ARC227 B - Know Your Place

各自の場所

考え方

仮に $B$ が構成できたとして、値 $i$ がどこに入れられるか考えてみる。
以下、順番は 0-indexed で表記する。

まず、条件を満たしている以上、$i$ 番目より前は全て $i$ 未満の数。
よって、$i$ 番目以後、次に $i$ 未満の値が初めて登場する前まで。
これが、値 $i$ を使用できる範囲である。

ということは、$i$ 番目は「それまでに未使用な $i$ 以下の数で最大のもの」でよい。

カウンティングソートと stack を利用すれば、計算量は $O(N)$ となる。

入力を受け取る。

n: 4
a: {3, 0, 1, 0}

各値の個数は、$0$ が $2$ 個、$1$ が $1$ 個、$2$ が $0$ 個、$3$ が $1$ 個である。

$i=0$ では、使用できる値として $0$ が $2$ 個ある。
最大の $0$ を採用し、残りは $0$ が $1$ 個となる。

$i=1$ では、値 $1$ も使用できるようになる。
使用できる未使用の値は $0,1$ なので、最大の $1$ を採用する。

$i=2$ では、新たに使用できる値 $2$ はない。
残っている値 $0$ を採用する。

$i=3$ では、値 $3$ が使用できるようになる。
これを採用する。

したがって、構築される数列は次のようになる。

b: {0, 1, 0, 3}

最後まで構築できたので、Yes とこの数列を出力する。

特になし。

特になし。