Codeforces Round #670 (Div. 2) A

A. Subset Mex

C++

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

int n;
int A[101], B[101];
vector<int> a;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        a.clear();
        int x;
        for(int i = 0; i < n; i++){
            cin >> x;
            a.push_back(x);
        }
        sort(a.begin(), a.end());
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        int last = a[0];
        A[last] = 1;
        for(int i = 1; i < n; i++){
            if(last == a[i])
                B[a[i]] = 1;
            else
                A[a[i]] = 1;
            last = a[i];
        }
        int ans = 0;
        for(int i = 0; i < 101; i++){
            if(A[i] == 0){
                ans += i;
                break;
            }
        }
        for(int i = 0; i < 101; i++){
            if(B[i] == 0){
                ans += i;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

주어진 수들을 두개의 집합으로 나누어 각각 mex 함수에 대입한 후 반환된 두 값의 합이 최대가 되도록 하는 문제이다.

mex 함수는 집합에 없는 자연수들 중 최소값을 반환하는 함수이다. (공집합일 경우는 0)

주어진 숫자들을 오름차순으로 정렬한 뒤 한 집합의 결과값이 최대가 되도록 수를 분배해주면 해결할 수 있다. A 배열을 최대가 되도록 정하고 이전의 값과 같은 수가 나오면 B 배열에, 다르면 A 배열에 집어넣도록 알고리즘을 작성했다.

후기

처음 참여해 본 코드포스 대회. 간단한 문제도 어휘력이 부족해 읽는 데 시간이 오래 걸렸다. 또 B번 그리디 문제에서 막혀 다른 문제는 건드려보지도 못했다. 결과는 다섯문제 중 A번 하나 풀고 Newbie 진입...