Codeforces #1496B Max and Mex

문제

https://codeforces.com/problemset/problem/1496/B

걸린 시간

-

풀이

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--){
        ll n, k;
        cin >> n >> k;
        set<int> a, s;
        int tmp;
        for(int i = 0; i < n; i++){
            cin >> tmp;
            a.insert(tmp);
        }
        if(a.find(0) == a.end()){
            s.insert(0);
        }
        for(int x : a){
            int low = x-1;
            int high = x+1;
            if(low >= 0 && a.find(low) == a.end()){
                s.insert(low);
            }
            if(high <= INF && a.find(high) == a.end()){
                s.insert(high);
            }
        }
        int me = *s.begin();
        int ma = *a.rbegin();
        int el = round((me*1.0+ma)/2);
        if(k == 0){
            cout << n << "\n";
        }
        else if(me < ma){
            if(a.find(el) != a.end()){
                cout << n << "\n";
            }
            else{
                cout << n+1 << "\n";
            }
        }
        else{
            cout << n+k << "\n";
        }
    }
    return 0;
}

예제를 5개 이상 풀어보니 대회때는 보이지 않았던 규칙들이 눈에 들어왔다. mex(S) 가 max(S) 보다 클 땐 ⌈(a+b)/2⌉ 값이 계속해서 1씩 증가되므로 n+k 가 답이고, 작을 땐 몇번을 반복해도 ⌈(a+b)/2⌉ 값이 동일하기 때문에 S 에 값이 존재한다면 n, 존재하지 않으면 n+1 이 답이된다.

문제를 푸는동안 자잘한 실수들이 많아서 따로 정리했다.

• 천장 함수가 있다고 무조건 올림하지 말자. "(rounded up)"을 보지 못하고 ceil 함수를 사용했다.
• mex 값을 구하는 방법으로 set 을 이용했는데 꼼꼼하지 못해 일부 케이스에선 제일 낮은 값이 0일 때 다른 값을 출력했다.
• k 값이 0 일때의 처리를 해주지 않았다.
• ⌈(a+b)/2⌉ 에서 a+b 에 괄호처리를 해주지 않았다.