概要
公式解説では、最小値の挙動に注目しています。私は最大値の挙動に注目して解いたので、解説しておきます。
私の解説では、$A_i+1$ のことを改めて $A_i$ と呼ぶことにします。つまり、cyclic shift する項数です。
解法
$N$ 項からなる数列 $A$ に対して、$K$ 回の操作を行うとき、
- 各項の行き先
- 各項が操作された（その項を先頭とする cyclic shift を行った）回数
を求める関数を $f(A)$ とします。$|A| \geq 2$ のとき、$f(A)$ を、より短い数列 $A’$ に対する計算結果 $f(A’)$ から求められることを示します。
$A_N < N$ のとき：
末尾が $N$ 未満のとき、すべての項が $N$ 未満です。よって、あらゆる cyclic shift の長さが $N-1$ 以下です。よって、末尾の項は永遠に不動です。末尾を除いた数列 $A’ = (A_1, \ldots, A_{N-1})$ に対して解けばよいです。
$A_N = N$ のとき
$A_i = N$ となる $i$ 全体を $I$ とします。
末尾の項が動く操作は、長さ $N$ の cyclic shift のみです。このような操作を行ったとき、再び末尾が $N$ になります。したがって、末尾は常に $N$ であることが分かります（どの $i\in I$ に対する $A_i$ 由来のものであるかは分かりません）。
すると、$A_i = N$ であるような項に対する操作を、長さ $N-1$ の cyclic shift に変更しても、最終的な数列は同じであることが分かります。$N$ を $N-1$ に変更して末尾を削除した数列 $A’$ に対する $f(A’)$ から、この場合の最終的な数列が分かります。
最終的な数列が求まっても、それぞれの $N$ がどの $i\in I$ 由来であるかがすぐには分かりません。$f(A’)$ の返り値として、各項の操作回数を持たせておくことにより、$i\in I$ であるような項に対する操作回数の合計が手に入ります。$A_i=N$ であるような項の相対的な位置関係は、それらの間での cyclic shift という形でしか変化しないことから、$i\in I$ であるような項の最終的な位置関係や操作回数が復元できます。
感想
おもしろい。既出ネタじゃなければ AGC-C,D くらいで出せそう。
