Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regularr Contest 133 A 問題 Erase by Value

AtCoder ARC ARC133 A問題 300 pts

問題

提出解答

問題の概要

整数列 $A=(A_i)_{i=1}^N$ が与えられる. $A$ に存在する整数 $x$ を1つ選び, $A$ から $x$ を全て取り除く.

この操作によってできる列 $A'$ のうち, 辞書式最小であるものを求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$

解法

$x$ として $a$ を選んだときに完成する列を $A^{(a)}$ と書く.

指定すべき $x$ は以下である.

$A$ が単調増加列であるとき
$x=A_N$ とするべきである. もし, $x=A_j (\neq A_N)$ だった場合, $A_k \neq A^{(a)}_{k}$ となる $j \leq k \lt N$ となる $k$ が存在するが, $A^{(a)}_{k}=A_{k+1}$ で, $l=1,2, \dots, k-1$ では $A^{(A_N)}_l=A^{(x)}_l$ で, $A^{(A_N)}_k=A_k \lt A_{k+1}=A^{(a)}_k$ となり, 辞書式最小にならない.
が単調増加列ではないとき
として, とすべきである. は未満になり, として
- $j \lt I$ であるならば, $A_1 \leq A_2 \leq \dots \leq A_j$ であるから, 操作後の列は $A^{(A_j)}$ 以上になる.
- $I \lt j$ であるならば, $A^{(A_j)}$ の第 $(I-1)$ 項までは $A^{(x)}$ と一致して, $A^{(x)}_I=A_{I+1} \lt A_I=A^{(A_j)}_I$ となり, やはり最小にはならない.

$A$ が単調増加列かどうか, そうでない場合, $I$ を求めるための計算はともに計算量 $O(N)$ で行うことができる.