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

問題概要

$ mex(a, b, c\cdots) $は$ a, b, c\cdots $のうちに含まれていない、最小の0以上の整数とする。

数列$ {A _ i} $と$ M $が与えられる。すべての$ A _ i $の連続した$ M $個の部分について、それぞれmexを考える。この時、$ |A| - M + 1 $個のmexの最小値を求めよ。

制約：$ 1 \leq |A| < M < 1.5 \times 10 ^ {6}, 0 \leq A _ i \leq |A| $

考え方

連続M個のmexを調べたいので、1つだけ見て、そこから首尾だけ変更して効率よく計算でいないか？
しかし、これはなかなかに厳しい。mexを馬鹿正直に計算するとどうしても$ O(|A _ i| \log M) $ぐらい最悪かかってしまう。巧妙にvectorで数の続いてる区間をもって、削除と挿入による差分更新も可能ではあるが、複数個に対応させようとすると断然厳しい実装量となる。
常套テク発想を逆転させる。 $ 0 \leq A _ I \leq |A| $を利用すると、たかだか答えの候補は$ A $通りしかないと抑えられる。そして、答えとして満たすかは小さい順番に試せばよさそう。
具体的にはこうする。$ x $が最終的なmexの最小値だとすると、すべての$ M $個連続する区間のmexは当然$ x $以上。mexが$ x $以上である条件は実は簡単に求められるので、あとは少し効率化すればAC。

考察

mex演算

Grundy数などでも使われる0以上の整数の集合に対するmex演算は、以下のようなstd::setを用いて計算できる。

std::set<int> S;//Sにmexを計算したい要素が入ってる。
int ans = 0;
while(S.count(ans) != 0){
    //Sにansが含まれていたら、ans + 1がSにまたあるかを確かめる。　なくなったら終わり。
    ans++;
}
//ansがmexとなる。

これは、Sの中の要素の最大を$ X $とすると、$ O(X \log |S|) $の計算量が最悪かかる。(Grundy数の場合は、$ X $は一般的に大きくなることが少なく、なったとしても均してみた時は大丈夫)　今回の場合、愚直にシミュレーションは不可能だ。

差分更新

では、長さ$ M $の連続列であることを利用して、常套テクの最初と最後だけを変更しての差分更新を考えてみる。しかし、先ほどのmexのアルゴリズムのままではこれは効率的には行えない。ほとんど変わってなくても、効率的に再利用が難しい。

一つの方針としては、std::setに入れるのではなく、std::vector<pair<int, int>>として、 $$ [連続の始まり, 連続の終わり] $$ の形で持つことである。例えば、$ |S| = {1, 2, 4, 5, 6, 9, 34} $なら、{{1, 2}, {4, 6}, {9}, {34}}として持ち、ここから要素を1つ削除 and 挿入は二分探索で該当する場所を探し当てて、行うことである。

しかし、この方法では同じ要素が複数ある場合の適用に難儀してしまう。一応丁寧にやれば可能ではあると思うが、実装量は恐ろしく多い。

ここでこの方針を置いておき、別方針で探るべきだ。

答えを仮定して

別方針として考えられるのは、答えはたかだか$ |A| $通りということだ。仮に答えが$ x $だとして、それが条件を満たすようにチェックできれば、$ x $を小さい順に試しておき初めて条件を満たしたものが答えでよい。(今回の求める連続列のmexの最小値はこの単調性がある)これは$ O(|A|) $のループしか回らない。(しかし、これで行くならばループの中は限りなく$ O(1) $出なければ間に合うことは難しいだろう)

仮に答えが$ x $であるとして、それが真であるには、次の条件を満たす必要がある。

どの長さ$ M $の連続列でも、mexが$ x $以上。

mexが$ x - 1 $より大きいとわかっているとき、$ x $がmexの最小値の候補としてあり得るかは、すべての$ A $の中の$ x $を見て、(先頭と後尾と)お互いと、$ M $個以上だけ間を空けていたら$ x $はmexの最小値となる。(そこの$ M $個以上の連続列では確実に$ x $は含まれていないが、$ x - 1 $以下は含まれているので、そこからとればmexの最小値は明らかに$ x $)

これは、すべての$ A[] $の値ごとに、要素としてどこにあるかをメモしておけば、$ x $が小さい順に確認するときに効率的に見ることができる。全体で計算量はたかだか$ O(|A|) $となる。