AGC 032 A - Limited Insertion

• 問題
• AC

$b'_i = b_{i+1}-1$として0-basedで考える。$k\in \{0, 1, ..., N-1\}$が与えられたとせよ。$b'_k$より左にある数（$b'_0, ..., b'_{k-1}$）が$b'_k$個より多く挿入されると、もう$b'_k$は挿入できない。また、$b'_k$より左にある数を少なくとも$b'_k$個挿入ずみでないと、$b'_k$はまだ挿入できない。したがって、$B = \{b'_i | b'_iより左の数がちょうどb'_i個挿入ずみ\}$から１つ選んで挿入する操作を$N$回繰り返せればそれが答えになるし、できなければ不可能である。ここでもう少し考えると、常に$B$の中でいちばん右にある数だけ調べれば良いことに気づく。というのも、$b'_i$より右にある数が挿入ずみかどうかは$b'_i$が挿入できるかどうかに影響しないからである。計算量は${\mathcal O}(n^2)$。

操作を逆順に見るとよりシンプルになるらしい。それは最初に検討するべきだった。