公式解説では、\(P\) を変換させて議論を進めていましたが、\(P\) のまま議論を進める方法を記述したいと思います。

以下の値を K-転倒数 と定義します。(ここだけの定義です)

• \(P_{i} > P_{j}\) かつ \(j - i \geq K\) を満たす \((i, j)\) の組の数

この値は \(1\) 回操作するごとにどのように変化するでしょう。\(5\) つの場合分けをします。

1: \(l \leq i - K\) について

\(l\) は \(i, j\) どちらとも \(K\) 以上離れているため、K-転倒数 の変化に対する寄与はありません。

2: \(i - K < l < \min(i + K, j - K + 1)\) について

\(l\) は \(j\) とのみ \(K\) 離れていてかつ、 \(l < j\) を満たします。 \(P_{j}\) の値は以前より大きくなっているため、\(l, j\) は swap しづらくなります。よって、K-転倒数 の変化に対する寄与は正ではありません。

3: \(\min(i + K, j - K + 1) \leq l < \max(i + K, j - K + 1)\) について

この条件を満たす \(l\) は \(i< l < j\) を満たします。 \(l\) からみて、前の値が小さくない、後ろの値が大きくなるので、 swap しづらくなります。よって、よって、K-転倒数 の変化に対する寄与は正ではありません。

4: \(\max(i + K, j - K + 1) \leq l < j + K\) について

\(l\) は \(i\) とのみ \(K\) 離れていてかつ、 \(i < l\) を満たします。 \(P_{i}\) の値は以前より小さくなっているため、\(i, l\) は swap しづらくなります。よって、K-転倒数 の変化に対する寄与は正ではありません。

5: \(j + K \leq l\) について

\(l\) は \(i, j\) どちらとも \(K\) 以上離れているため、K-転倒数 の変化に対する寄与はありません。

以上より、K-転倒数 は操作するごとに必ず \(1\) 以上小さくなります。自分は 2番目と 4 番目についてが直感と違かったためこの問題を難しく感じました。

よって、操作回数の自明な上界は \(P\) の K-転倒数 で、この値の回数操作することができるやり方が実際に存在します。その一例を記します。

最初の \(P_{i}\) が大きい順に \(i\) をみて、以下の操作をします。

• 数列 \(L\) を \(j \leq i - K\) かつ \(P_{j} > P_{i}\) を満たす \(j\) を \(P_{j}\) が小さい順に並べたものとする。そして、 \(j = L_{1}, L_{2}, \dots L_{|L|}\) の順に、 \(\mathrm{swap}(P_{j}, P_{i})\) をする。

この操作は可能かつ操作回数の上限であることが示せるので、これを元に出力すれば AC が得られます。

時間計算量はソートがボトルネックとなって、\(O(N^{2}\log(N))\) です。

C++ 実装例

\(P\) が順列であることを思い出すと、\(O(N ^ {2})\) にすることも可能です。実装がシンプルになるかもしれません。

C++ 実装例