AtCoder Beginner Contest 245 B問題 Mex - Kazun の競プロ記録

$A=(A_1, \dots, A_N)$ に対して, $\operatorname{mex} A$ を求めよ.

ただし, 非負整数列 $S=(S_i)$ に対して, $\operatorname{mex} S=\min \{n \in \mathbb{N} \mid \not \exists i {\rm ~s.t.~} A_i=n\}$ とする.

$N$ 要素からなる非負整数列 $A$ に対して, $0 \leq \operatorname{mex} A \leq N+1$ が成り立つ.

よって, このことから, $x=0,1,\dots, N+1$ に対して, $x$ は $A$ の要素として存在するか? という問に答え, 存在しないような $x$ の最小値を答えれば良い.

長さ $N$ の列に対するある要素の存在判定は愚直にすれば時間計算量 $O(N)$ で, 集合や予め要素カウントをしておくことにより, $O(1)$ で判定できる.

従って, 全体で $O(N^2)$ や $O(N)$ 時間で最小除外数 (mex) を求めることができた.