以下 \(\mathrm{left\_rotate}\) を列の先頭の要素を取り出し列の最後に付け加える操作とする。反対に \(\mathrm{right\_rotate}\) を列の最後の要素を取り出し列の先頭に付け加える操作とする。 すると、一回の操作は重ならない連続部分列についてそれぞれ \(\mathrm{left\_rotate}\) を行う操作となる。 また、任意の \(t\) について \(t\) 回目の操作で同じ連続部分列に含まれるならば、 \(t+1\) 回目の操作でも同じ連続部分列に含まれる必要がある。

部分点解法

\(v(l,r,k)\) を以下の様に定義する

• \((P_l,\cdots,P_{r−1})\) を昇順に並び替えた列を \((P'_1,\cdots, P'_{r-l})\) として、\(v(l, r, k) = (P'_k,\cdots,P'_{r-l},P'_1, \cdots, P'_{k-1})\)。

次に \(\mathrm{dp}[l][r][k]\)を以下のように定義する。

• \(\mathrm{dp}[l][r][k] =\) \((P_l,\cdots,P_{r−1})\) を \(v(l, r, k)\) に一致させるのに必要な操作の最小値

このとき、この \(\mathrm{dp}\) テーブルは以下の \(2\) 種類の遷移によって表せる

• \(i=l+1,\cdots,r−1, 0\leq x<i−l, 0 \leq y<r−i, 0\leq z<r−l\) に対し、\(v(l,i,x)\) と \(v(i,r,y)\) を結合して\(v(l,r,z)\) となるとき、\(\displaystyle\mathrm{dp}[l][r][z] \leftarrow \min(\mathrm{dp}[l][r][z],\max(\mathrm{dp}[l][i][x],\mathrm{dp}[i][r][y]))\) と遷移できる。ここで、\(\mathrm{left\_rotate}\) の形から、各 \(l,r,i\) について考えられる \((x,y,z)\) の組は高々 \(1\) つしかない。

• \(0\leq x<r−l,1\leq k\leq r−l\) について、\(v(l,r,x)\)を \(k\) 回 \(\mathrm{left\_rotate}\) すると \(v(l,r,(x+k) \bmod{(r−l)})\) になることから、\(\displaystyle\mathrm{dp}[l][r][(x+k)\bmod{(r−l)}] \leftarrow \min(\mathrm{dp}[l][r][(x+k)\bmod{(r−l)}],dp[l][r][x]+k)\) と遷移できる。この処理は各 \(l,r\) に対して、スライド最小値を用いて \(O(N)\) 時間でできる。

\(\mathrm{dp}[1][N][1]\) が解となり、全体で \(O(N^3)\) の計算時間がかかる。

満点解法

\(Q=P^{-1}\) とし、逆順に操作を行って、 \(Q\) を昇順に並べることを考える。すると、一回の操作は重ならない連続部分列についてそれぞれ \(\mathrm{right\_rotate}\) を行う操作となる。また、解説にて以下の表記を使用する。

• 列 \(a\) が \(a_1\) と \(a_2\) をこの順で繋げて得られる列であるとき、 \(a=a_1+a_2\) と表記する
• 列 \(a\) に関する解を \(f(a)\) とする
• 列 \(a = a_1+a_2+\dots+a_{\ell}\) が以下の条件を満たすとき \(a_1, a_2, \dots, a_{\ell}\) に分割可能であるとする。
  • \(a_1\) が \((1,\dots, |a_1|)\) を並び替えたもの
  • \(a_2\) が \((|a_1|+1,\dots, |a_1|+|a_2|)\) を並び替えたもの
  • \(\vdots\)
  • \(a_{\ell}\) が \((\sum_{i=1}^{\ell-1}|a_i|+1, \dots, \sum_{i=1}^{\ell}|a_i|)\) を並び替えたもの

すると、以下の貪欲が最適となる（証明は後述）。

• はじめて列が \(2\) つ以上に分割可能になるまで \(\mathrm{right\_rotate}\) する。
• 列を分割後の個数が最大となる様に分割し、分割後の列についてそれぞれ独立に操作を行う
  • すなわち、列 \(a = a_1+a_2+\dots+a_{\ell}\) が \(a_1, a_2, \dots, a_{\ell}\) に分割可能である時、 \(f(a) = \max{(\{f(a_1), f(a_2), \dots, f(a_{\ell}) \})}\) となる

このことから、分割可能になるまで \(\mathrm{right\_rotate}\) を繰り返し、分割した問題については再帰的に解くことでこの問題を解くことができる。 また、はじめて \(2\) つ以上に分割されるまでの \(\mathrm{right\_rotate}\) の繰り返し回数は後述のアルゴリズムにより列の長さに対して線形時間で求められ、分割の仕方も列の長さに対して線形で求まる。このアルゴリズムは再帰の深さが高々 \(N\) であり、各深さについて合計 \(N\) 要素について解くことになるため、全体で \(O(N^2)\) の計算時間がかかる。

はじめて \(2\) 個以上に分割されるまでの \(\mathrm{right\_rotate}\) の繰り返し回数を求めるアルゴリズム

列 \(x = ( x_1 , x_2 , \dots , x_N )\) を \(( 1 , 2 , \dots , N )\) の順列とする。 値の昇順に見る（値の集合は \(\{ 1 , 2 , \dots , N \}\) であるので、 \(O(N)\) で見れる）。 \(01\) 列 \(A = ( A_1 , ⋯ , A_N )\) を用意し、円環をなしている、すなわち \(A_N\) の右隣は \(A_1\) であるとみなす。

• 最初すべての値は \(0\) とする。
• \(i = 1 \dots N - 1\) について以下を行う
  • 値の昇順にみて、\(Q_j = i\) となるような \(j\) についてを \(A_j \leftarrow 1\) に変える。
  • \(A\) 上で \(1\) であるようなものが \(1\) つの連続区間になっていれば先頭が \(i\) 要素である様に分割可能であるが、\(0\) と \(1\) が隣り合う \(\mathrm{index}\) を管理し、分割可能かどうかと何回 \(\mathrm{right\_rotate}\) を繰り返す必要があるかを \(O(1)\) で求める
• \(i = 1 \dots N-1\) に対して得られた \(\mathrm{right\_rotate}\) の繰り返し回数のうち最小のものを返す

貪欲が最適となる証明

先に以下の補題を示す

補題：列 \(a\) と、その部分列 \(a'\) について、 \(f(a') \leq f(a)\) がなりたつ

• \(\mathrm{right\_rotate}\) 操作を行うとき、部分列を抜き出すと、\(\mathrm{right\_rotate}\) 操作か何も変化しない操作になる
• 何もしない操作は、その区間の操作開始を \(1\) だけ遅らせることで消去することが出来る
• よって、 \(a\) のソート列からそれより手数が多くならない \(a'\) のソート列を作成できる

これを踏まえて証明を行う

長さ \(n\) の列 \(a= a_1 + a_2\) について、 \(a_1, a_2\) に分割出来るなら \(f(a) = \max(f(a_1),f(a_2))\) となることを示せばよい（分割可能でない場合、必ず列全体に対し \(\mathrm{right\_rotate}\) を行わなければならないため分割可能である場合を考えればよい）。

長さ \(n = 1 , 2\) は明らかである。 長さ \(m \leq n − 1\) についてこれが成り立つと仮定する。 列 \(t\) を長さ \(n\) の分割可能な列とする。また、列 \(t\) を \(1\) 回以上 \(\mathrm{right\_rotate}\) し、はじめて分割可能になる列を \(t'\) とする。ここで、(\(t\) の分割で得られる先頭の連続部分列の長さ)と(\(t'\) の分割で得られる先頭の連続部分列の長さ)の大小関係で場合分けする

（\(t\) の分割で得られる先頭の連続部分列の長さ）=（\(t'\) の分割で得られる先頭の連続部分列の長さ）のとき

\(t\) の分割で得られる先頭の連続部分列、と \(t'\) の分割で得られる先頭の連続部分列は、互いに同一の要素からなる列の並び替えとなるが、これは \(\mathrm{right\_rotate}\) の繰り返しによって得られる列において、\(t=t'\) に限られる。よって、自明に成り立つ。

（\(t\) の分割で得られる先頭の連続部分列の長さ）<（\(t'\) の分割で得られる先頭の連続部分列の長さ）のとき

\(t= t_1 + t_2 + t_3 + t_4, t'=t_4 + t_1 + t_2 + t_3\) とおいて、\(t\) の分割で得られる先頭の連続部分列を \(t_1\) 、\(t'\) の分割で得られる先頭の連続部分列を \(t_4 + t_1 + t_2\) であるとしてよい（\(|t_1|,|t_3|,|t_4|>0, |t_2|\geq 0\)）。

このとき、

• \(t\) をそのまま分割して得られる解は \(\max(f(t_1), f(t_2 + t_3 + t_4))\)
• \(t\) を \(t'\) になるまで \(\mathrm{right\_rotate}\) した後得られる解は \(|t_4| + \max(f(t_4 + t_1 + t_2), f(t_3))\)

\(f(t_2 + t_3 + t_4)\) を評価する。\(|t_4|\) 回 \(\mathrm{right\_rotate}\) を行えば、 \(t_4+t_2\) と \(t_3\) に分割できるが、それ以下の回数で分割できるとすると、\(t'\) の定義に反する。よって、 \(|t_2 + t_3 + t_4|<n\) により、

\[ f(t_2 + t_3 + t_4) = |t_4| + \max(f(t_4 + t_2),f(t_3)) \]

であることから、

\[\begin{aligned} & \max(f(t_1), f(t_2 + t_3 + t_4)) \\ &\quad= \max(f(t_1), |t_4| + \max(f(t_4 + t_2),f(t_3)))\\ &\quad\leq |t_4|+\max(f(t_1),f(t_4+t_2),f(t_3))\\ &\quad\leq |t_4|+\max(f(t_4+t_1+t_2),f(t_3)) \end{aligned}\]

よって示された。

（\(t\) の分割で得られる先頭の連続部分列の長さ）>（\(t'\) の分割で得られる先頭の連続部分列の長さ）のとき

\(t=t_4 + t_1 + t_2 + t_3, t'= t_1 + t_2 + t_3 + t_4\) とおいて、\(t\) の分割で得られる先頭の連続部分列を \(t_4 + t_1 + t_2\) 、\(t'\) の分割で得られる先頭の連続部分列を \(t_1\) とすると下記の様に表せ、同様に不等式が成り立つ。

• \(t\) をそのまま分割して得られる解は \(\max(f(t_4 + t_1 + t_2), f(t_3))\)
• \(t\) を \(t'\) になるまで \(\mathrm{right\_rotate}\) した後得られる解は \(|t_1| + |t_2| + |t_3| + \max(f(t_1), f(t_2 + t_3 + t_4))\)

列 \(t_4+t_1+t_2\) は、 \(|t_1|+|t_2|\) 回の操作後に、 \(t_1\) と \(t_2+t_4\) に分割可能であることから、 \(f(t_4+t_1+t_2) \leq |t_1|+|t_2|+\max(f(t_1), f(t_2+t_4))\)。

よって、

\[\begin{aligned} &\max(f(t_4 + t_1 + t_2), f(t_3)) \\ &\quad\leq \max(|t_1|+|t_2|+\max(f(t_1),f(t_2+t_4)), f(t_3)) \\ &\quad\leq |t_1|+|t_2|+|t_3|+\max(f(t_1),f(t_2+t_4),f(t_3))\\ &\quad\leq |t_1|+|t_2|+|t_3|+\max(f(t_1),f(t_2+t_3+t_4)) \end{aligned}\]

より示された。

ゆえに、列 \(t\) が分割可能であるならば即座に分割するのが最適であり、数学的帰納法により任意の長さについてこれはなりたつ。