[코드포스 / Codeforces] Round #899 (Div. 2)

Codeforces Round #899 (Div. 2)

문제 세트는 여기서 확인할 수 있다.

---

문제

A. Increasing Sequence (AC / 6 min)

배열 a를 입력받고 조건을 만족하는 b의 n번째 원소의 최솟값을 출력하는 문제.

b는 반드시 오름차순이어야 하고 b의 n번째 원소가 최소가 되기 위해선 a의 1번째 원소는 1부터 가능한지 검사한다.

a와 b의 i번째 원소가 같으면 안되므로 x = 1이라는 변수를 만들고 a의 각 원소에 대해 같으면 +2, 아니면 +1 한다.

기본적으로 오름차순이어야 하니까 +1인데, 만약 원소가 a와 같으면 1 더 증가시키면 된다.

x는 b의 n번째 원소 + 1 이므로 x-1 출력.

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

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    int x = 1;
    for (int i = 0; i < n; i++) {
      if (a[i] == x) {
        x++;
      }
      x++;
    }
    cout << x - 1 << '\n';
  }
  return 0;
}

 

B.Sets and Union (WA)

n개의 집합이 들어오고, n개의 집합 중 적절히 몇개 골라서 만든 합집합을 s라 하면 전체 합집합보다 크기가 작은 s중에 가장 큰 s의 크기를 구하는 문제.

처음에는 모든 조합을 확인하는 백트랙킹 코드를 구현했고, 당연히 결과는 TLE

모든 가능한 s를 입력 받으면서 미리 만들었더니 MLE

 

이후 업솔빙을 시도했고.. 풀이를 들었는데 분명..

1~50 사이의 수가 들어오므로 min(1을 포함하지 않는 모든 집합들의 합집합의 크기, 2를 포함하지 않는 모든 집합들의 합집합의 크기, ...)를 구하면 된다.

근데 이걸 직접 구현하니 당연히 TLE가 되어버렸고 결론은 비트마스킹을 해야한다.

 

이 풀이는 어느 한 외국인 분의 코드를 참고해서 다시 한 번 짜봤다.

i(1~50)를 포함하는 집합의 수를 세는 배열 cnt

i(1~50)를 가지는 집합의 번호를 모아놓은 배열 val

집합들의 배열 v

ans는 모든 집합의 합집합의 크기

예를 들어 1을 포함하는 집합이 없으면 넘어가고, 2를 포함하는 집합이 1개 이상이라면 2를 포함하는 집합들의 모든 원소마다 개수를 세어준다. 그리고 전체 집합에서 1~50 각각의 개수를 비교하고 0이 아니면서 같다면 ans에서 1씩 빼준다. 왜냐하면 같다는 것은 전체 집합에서 2를 포함하는 집합들을 제거했을 때 해당 수도 사라진다는 뜻이기 때문.

따라서 1~50 모두 탐색한 다음 ans의 최댓값을 출력.

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

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, ans = 0;
    cin >> n;
    vector<vector<int>> v(n), val(51);
    int cnt[51] = {0};
    for (int i = 0; i < n; i++) {
      int k;
      cin >> k;
      for (int j = 0; j < k; j++) {
        int x;
        cin >> x;
        v[i].push_back(x);
        val[x].push_back(i);
        cnt[x]++;
        if (cnt[x] == 1)
          ans++;
      }
    }
    vector<int> cn(51, 0);
    int an = 0;
    for (int i = 1; i <= 50; i++) {
      if (val[i].size() == 0)
        continue;
      fill(cn.begin(), cn.end(), 0);
      int tmp = ans;
      for (int j : val[i]) {
        for (int k : v[j]) {
          cn[k]++;
        }
      }
      for (int j = 1; j <= 50; j++) {
        if (cnt[j] - cn[j] == 0 && cnt[j] > 0)
          tmp--;
      }
      if (tmp != ans)
        an = max(an, tmp);
    }
    cout << an << '\n';
  }
  return 0;
}

---

총평

너무너무너무 어렵다. div 2 1솔로 끝낸 것은 또 처음이다. 구현이 어렵고 복잡하고 머리 많이 써야했고 비트마스킹에 한 번 크게 데인 듯 한 대회였다.