TOC

1. A : Not Found
2. B : Grid Rotation
3. C : Cycle Graph?
4. D : Goin’ to the Zoo

A : Not Found

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

constexpr int INF = numeric_limits<int>::max();

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  bitset<26> bs;
  for (char ch : s) {
    bs[ch-97] = true;
  }
  for (int i=0;i<26;i++) {
    if (!bs[i]) {
      cout << (char) (i + 97);
      break;
    }
  }
  return 0;
}

B : Grid Rotation

• 시계방향으로 돌려가면서 얼마나 차이나나 비교하면 된다.

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

constexpr int INF = numeric_limits<int>::max();

int S[100][100];
int T[100][100];
int tmp[100][100];
int n;

void rotateS() {
  for (int i=0;i<n;i++) {
    for (int j=0;j<n;j++) {
      tmp[j][n-i-1]=S[i][j];
    }
  }
  memcpy(S, tmp, 100 * 100 * sizeof(int));
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  for (int i=0;i<n;i++) {
    string s; cin >> s;
    for (int j=0;j<n;j++) {
      S[i][j] = s[j] == '#';
    }
  }
  for (int i=0;i<n;i++) {
    string s; cin >> s;
    for (int j=0;j<n;j++) {
      T[i][j] = s[j] == '#';
    }
  }

  int ans = INF;
  for (int k=0;k<4;k++) {
    int res = k;
    for (int i=0;i<n;i++) {
      for (int j=0;j<n;j++) {
        res += S[i][j] != T[i][j];
      }
    }
    ans = min(ans, res);
    rotateS();
  }
  cout << ans;

  return 0;
}

C : Cycle Graph?

• 그래프 안에 사이클이 있냐가 아님을 유의하자.
• 주어진 그래프 가 사이클 그래프려면 다음 두 가지 조건을 만족해야 한다.
  1. 의 모든 정점의 차수가 2
  2. 는 연결된 그래프

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

constexpr int INF = numeric_limits<int>::max();

vector<vi> G;
vector<bool> visited;

void dfs(int u) {
  if (visited[u]) return;
  visited[u] = true;

  for (int v : G[u]) {
    dfs(v);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  if (n != m) {
    cout << "No";
    return 0;
  }
  G.resize(n+1);
  visited.resize(n+1,false);
  for (int i=0;i<m;i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  for (int u=1;u<=n;u++) {
    if (G[u].size() != 2) {
      cout << "No";
      return 0;
    }
  }

  dfs(1);
  for (int u=1;u<=n;u++) {
    if (!visited[u]) {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";

  return 0;
}

D : Goin’ to the Zoo

• 비트마스킹을 떠올렸다. 근데 각 비트가 0, 1, 2가 저장되는.
• 시간복잡도는 이 되겠다.

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vi C(n+1);
  for (int i=1;i<=n;i++)
    cin >> C[i];
  vector<vi> ani(n+1); // zoo -> animal[]
  for (int i=1;i<=m;i++) {
    int k; cin >> k;
    for (int j=0;j<k;j++) {
      int z; cin >> z;
      ani[z].push_back(i);
    }
  }

  ll ans = numeric_limits<ll>::max();
  for (int i=0;i<(int)pow(3,n);i++) {
    vi cnt(m+1,0);
    bitset<101> seen;
    ll cost=0;
    for (int j=i,z=1;j>0;j/=3,z++) {
      cost += C[z] * (j%3);
      for (int a : ani[z]) {
        cnt[a] += j%3;
        seen[a] = cnt[a] >= 2;
      }
    }
    if (seen.count() == m) {
      ans = min(ans, cost);
    }
  }
  cout << ans;

  return 0;
}