AGC024 B - Backfront - ツバサの備忘録

問題

まず、最悪 $N$ 手でソートすることができます。これは、 $N$ から順番に、一番左側に移動していけばよいです。
ということで、さらに効率的な方法を探ります。
今回の操作では、両端に数字を移動させることはできますが、逆に真ん中に数字を挿入することはできません。
ということで、操作しない数字を $K$ 個と決めた場合に、その $K$ 個の数字だけを取り出して元の順番のまま並べると、 $i,i+1,i+2,...i+K-1$ となっている必要があります。
逆に、この条件を満たす数字 $K$ 個が存在する場合、 $N-K$ 手で昇順にソートすることができます。
$i-1,i-2,...1$ の順番で数字を左側の先頭に、 $i+K, i+K+1, ...N$ の順番で数字を右側の最後尾にもっていくことによって条件を満たすことができます。
ということで、最終的に求めたいのは、 $i,i+1,i+2...i+K-1$ と並んでいる(連続しているとは限らない)部分列の最長の長さ $K$ です。
これは、 $X_{p_{i}} = i$ となっている数列 $X$ について、 $X$ の先頭から見ていき、 $X_{i} + 1 = X_{i+1}$ となっている区間の最長の部分を探せばよく、これは $O(N)$ で調べることができます。
あとは、最長の長さ $K$ を求め、 $N-K$ を計算すれば答えとなります。

感想

AGCの500点にしては…？と思う問題でした。それぐらいすんなり解けたので、実力が伸びているみたいで（と思いたいです）うれしいです。