E - Mex Min

問題

長さの整数列が与えられる．
を満たすすべての整数について，を求め，その最小値を答えよ
atcoder.jp

解法

解法1

なので，個の数字をstd::setで管理すれば解ける

Submission #33224842 - AtCoder Beginner Contest 194

解法2

上記の解法では，更新部分はたかだか２つなので，その更新を行いつつsetを用いてを求めていた．
ある部分列に対してのは，更新前のがわかっていれば，更新部分を見るだけで良い．言い換えると，部分列から外れる数字がの候補になりうる．

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N,M;
    cin >> N >> M;
    
    vector<int>A(N);
    vector<int>count(N + 1, 0LL);
    
    for(auto& a : A)
        cin >> a;
    
    for(int i = 0; i < M; ++i)
        count[A[i]] += 1;
    
    int mex = INT_MAX;
    
    for(int i = 0; i < count.size() && mex == INT_MAX; ++i)
        if(count[i] == 0)
            mex = i;
    for(int i = 0; i + M < A.size(); ++i){
        count[A[i]] -= 1;
        count[A[i + M]] += 1;
        
        if(count[A[i]] == 0){
            mex = min(mex, A[i]);
        }
    }
    
    cout << mex << endl;
}