Codeforces Round #708 (Div. 2) A

A. Meximization

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        vector<int> b(101, 0);
        for(int i : a) b[i]++;
        for(int i = 0; i <= 100; i++){
            if(b[i] == 0) break;
            b[i]--;
            cout << i << " ";
        }
        for(int i = 0; i <= 100; i++)
            for(int j = 0; j < b[i]; j++)
                cout << i << " ";
        cout << "\n";
    }
    return 0;
}

Mex 함수는 배열에서 0을 포함한 양의 정수 중 출현하지 않은 제일 작은 값을 반환한다. 크기가 n 인 배열 a 를 적절히 재배치하여 배열 b 를 만든다고 할 때, b1 부터 b1, ... ,bn 까지 차례대로 Mex 함수를 취하여 모두를 합한 값이 최대가 되도록 하는 배치를 찾아야 한다.

값이 최대가 되기 위해서는 Mex 한 값이 바뀌지 않을 때 까지 작은 수 부터 차례대로 하나씩 나열한 후 남은 값들을 순서에 상관없이 배치해주면 된다.

후기

B, C 는 constructive algorithm, 정수론 문제로 시간이 더 많았어도 솔루션을 떠올리지 못했을 것 같다.