はじめに

アウトプットと、自分の理解のために、自分の理解についてまとめています。

問題

方針

配列によるMexの管理

最初のMexは、先頭の要素からM個の要素を見ることで求められる。

Mexの求め方は、配列 $cnt$ を用意して、M個の要素の出現回数をカウントする。そして、配列のindexを0から見たときに1度もカウントされていない値（ $cnt \left[ v \right] = 0$ となる $v$ )がMexになる。

次に、最初のMexと次のMexの違いについて考える。

最初のMexは、

次のMexは、

一般化して考えると、Mexを求めるための $A_i$ からの整数列は、 $A _ { i-1}$ がなくなって、 $A _ {M+i}$ が追加される。

配列 $cnt$ の変化について考えると、 $cnt \left[ A_0 \right]-1$ されて、 $cnt \left[ A_M \right] + 1$ というように更新される。

このとき、Mexがどう変化するかについて考えると、Mexに成りうる値は、 $-1$ された $A_0$ である。（ $cnt \left[ 0 \right]$ から一番最初に現れる $cnt \left[ v \right] = 0$ となる $v$ がMexとなるので、 $cnt \left[ A_0 \right] = 0$ となれば、その値がMexとなりうる。）