(出題: hotman)

\(\sum_{i = 1} ^ N |A_i - i|\) で数列 \(A\) のポテンシャルを定義します。コスト \(1\) あたり、ポテンシャルは最大で \(2\) 減らすことができます。

よって、コスト \(\dfrac{\sum_{i = 1}^{N} |A_i - i|}{2} = C\) は明らかに下界を与えます。

以下、実際にこのコストで操作列が構成できることを示します。

最終的にソート済みの数列が得られる操作列について、コストが \(C\) であることと、swap 操作によって、「無駄な」動きがないことは同値です。(ここで、無駄な動きとは swap によって、\(A_i\) が位置 \(i\) から遠ざかってしまったり飛び越してしまったりするコスト \(1\) あたりのポテンシャルの減らし方が \(2\) より小さくなってしまうような操作を指します。)

以下のようなアルゴリズムは無駄な動きをすることなく操作を完了できます。

• \(A_i = 1, \ldots, N\) の順に操作する。
  • 現在の \(A_i\) の位置を \(p\) とする。\(j = p - 1, \ldots, i \) の順番で見ていき、\(A_j \ge p\) となったとき、\(A_i, A_j\) を swap する。

この操作が無駄な動きをしていないことは明らかです。 ソート済みの配列が得られることは、簡単な背理法もしくは帰納法で示すことができます。

時間計算量は \(O\left(N ^2 \right)\) です。