Mex Min [AtCoder Beginner Contest 194 E]

https://atcoder.jp/contests/abc194/tasks/abc194_e

前提知識

• 二分探索
• （しゃくとり法みたいな考え方）

解説

https://atcoder.jp/contests/abc194/submissions/20735986

二分探索としゃくとり法っぽい考え方を使用して問題を解く。
ちなみにmexという関数は競技プログラミングではまあまあ出てくる。

二分探索

どちらかというとしゃくとり法でやろうと思ってから思いついた。
check(limit) := mexの最小値がlimit以下か
という判定関数を用意して判定を行う。
一見急に出てきたもののように見えるが、少し制限の弱い問題なら解く方法があるという場合に、
そういう問題と二分探索を組み合わせて答えを導くという問題として典型化できる。
（ちょっと無理矢理かも）

しゃくとり法っぽくやる

[0,M-1]の範囲のmexを計算して、次に[1,M]の範囲のmexを計算するときは、差分はA[0],A[M]しかないのだから、
前の計算結果をうまく使うことはできないかと考える。
mexの計算では、ある数が使用されているかという部分が重要なので、
cnt[x] := ある範囲においてA[i]=xを満たすiが何個あるか
というのを使えば、使用されているかどうかが管理できそうだ。
この配列の使用を前提とすると、差分A[0],A[M]については、cnt[A[0]]--, cnt[A[M]]++をすればいいだけなので、
とても高速に計算ができる。
だが、mexが要求している、含まれない最小の数というのは意外と取ってきにくい。

どう活用できるか

cntを使って含まれない最小の数を直接得ることは難しそうだが、usedという配列を別途用意しておき
cnt[x]=0でcnt[x]++されたら、used++
cnt[x]=1でcnt[x]--されたら、used--
することで、何個の数が使用されているかは高速に割り出すことができる。
ここでlimit以下という条件を追加して、limit以下で使われている数は何個あるかということを判定できるようにしておくと、
ある区間の計算を終えた後、used≦limitを満たせばlimit以下のmexが最低でも取り出せることが分かる。
（＜ではないか？と思うかもしれないが、limitが0-indexedなので、≦となる）

本番では最後が思いついてそれから二分探索だった。
計算量は全体でO(NlogN)

int N, M, A[2010101];
//---------------------------------------------------------------------------------------------------
int cnt[2010101];
bool check(int limit) {
    rep(i, 0, N) cnt[i] = 0;
    int placed = 0;
    rep(i, 0, M) {
        if (cnt[A[i]] == 0 && A[i] <= limit) placed++;
        cnt[A[i]]++;
    }
    if (placed <= limit) return true;
    rep(i, M, N) {
        if (cnt[A[i - M]] == 1 && A[i - M] <= limit) placed--;
        cnt[A[i - M]]--;
        if (cnt[A[i]] == 0 && A[i] <= limit) placed++;
        cnt[A[i]]++;

        if (placed <= limit) return true;
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    
    int ng = -1, ok = N;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}