AtCoder Beginner Contest 272 E問題 Add and Mex

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ がある. 次の操作を $M$ 回行う.

各操作後において, $A$ に含まれない最小の非負整数を求めよ.

一般的に, 以下が成り立つ.

長さが $K$ の整数列 $B$ において, $B$ に含まれない最小の非負整数は $0$ 以上 $K$ 以下である.

よって, 各操作の各項において, $0$ 以上 $N$ 未満でない場合, その項は考慮する必要はないことがわかる.

第 $i$ 項目において, $j$ 回目の操作後は $A_i+ij$ になる. これが $0$ 以上 $N$ 以下 (未満でも良いが, 議論を楽にするために以下とする) になるためには

$0 \leq A_i+ij \leq N \iff \left \lceil \dfrac{-A_i}{i} \right \rceil \leq j \leq \left \lfloor \dfrac{N-A_i}{i} \right \rfloor$

となる.

このような整数 $j$ の個数は高々 $\dfrac{N}{i}$ 個である. よって, $0$ 以上 $N$ 以下になるような操作回数と項の組の総和は

$\displaystyle X=\sum_{i=1}^M \dfrac{N}{i}$

であるが, 調和級数によって, $X=O(N \log N)$ であることがわかる.

よって, $N \leq 2 \times 10^5$ であるから, $0$ 以上 $N$ 以下になるような操作回数の場合に着目すればよい.

各操作回数ごとに登場した整数を集合で管理することによって, 各操作回数における $A$ に含まれない最小の非負整数を全体で $O(N \log N)$ 時間で求めることが出来る.

Kazun の競プロ記録