こどふぉってちょいちょいMEXが出てきますね。

問題

https://codeforces.com/contest/1375/problem/D

問題概要

長さnの配列が与えられる。各項の値は0からnの間の整数である。

あなたは、配列の任意の項を選択し、その時点での配列のMEXで置き換えることができる。

上記の操作を2n回以下行って、配列を広義単調増加にせよ。なお、それが常に実行可能であることは証明できる。

考察

とりあえず、すべての要素を $a_i = i$ にしてしまえば、手っ取り早く単調増加にできるのだろうなということは容易に想像できます。それを実現するために、その時点でのMEXをindex (0-indexed) が一致するところに入れてしまえばよいと考えて実行してみます。

例えば初期の配列が{2, 0, 3}だとして、この時点でのMEXは1なので、1番目に1をいれて{2, 1, 3}となり、MEXは0になるので0番目に0をいれて{0, 1, 3}とすれば、単調増加になり完成です。*1

ただし、これだけでは上手くいかなくて、例えばサンプルの2番目、{2, 1, 0}の場合（つまり0から順にすべての数が一つずつ使われている場合）だとMEXはnになってしまい、indexは0からn-1までしかありませんから、挿入する位置がありません。なので適当な位置を置き換えなければならないのですが、すでに $a_i = i$ となっているところを置き換えるのは無駄なので、まだそうなっていないところを置けばよさそうです。

先のサンプルだと{2, 1, 0}0番目が0ではないので、そこを置き換えます。{3, 1, 0}となります。MEXは2になったので2番目を置き換えて{3, 1, 2}となります。MEXは0になったので0番目を置き換えて{0, 1, 2}となり、完成です。

ちなみに、まだ $a_i = i$ になっていないところをどうやって探すか、ですが、すでに $a_i = i$ となっているindexを集めた配列を作ると、それのMEXがまだ $a_i = i$ になっていないindexのうちの最小のもの、になります。なので、特に深く考えずとも、メインの配列のMEXを取得する処理を流用すればよいので楽です。（この問題の場合）　まあ別にsetとか使えばよい話ではありますが。

なお、MEX=nのとき、配列の任意の要素は $n \gt a_i$ なので、任意の要素をnで置き換えたあとのMEXは必ずnより小さくなります。最悪でも、このセットをn回、つまり計2n回行えば、すべての要素を $a_i = i$ にすることが可能なので、回数の条件は満たすことができます。