AtCoder Regular Contest 110 F - Esoswap

面白い解法で解けたので (流石に既出かもしれない)

解法

これだけです．何をしているかというと，数列の後ろから順番に同じ場所を $N-1$ 回ずつ連続して選択しています．

順列 $P$ を読まなくても解けるのが個人的に面白いと思った部分です．

N = int(input())
print(N * (N - 1))
for i in range(N):
    for _ in range(N - 1):
        print(N - i - 1)

提出すると確かに AC を取れますが，本当に正しいのでしょうか？

正当性

まず，添え字 $k$ を連続して選択したときの $P _ k$ の値の変化を考えます．

少し実験すると，

$\begin{aligned} (\star):\text{「} &\text{添え字 $k$ を連続して選択したとき，$P _ k = 0$ となるまでは毎回異なる値が現れ，}\\ &\text{$P _ k = 0$ になってからは変化しない」} \end{aligned}$

という性質がありそうだと気づきます．

$P _ k = x$ のとき，添え字 $k$ を選択すると $x$ の位置は $k + x \bmod N$ へと移ります．従って，再び $P _ k = x$ となるためには， $P _ k = y\in\{0,\ldots,N-1\}\;\mathrm{s.t.}\;k + y \equiv k + x$ となる必要があります．そして，これを満たすのは $y=x$ に限られます．つまり，2 回以上同じ値となるのは $x=0$ しかありえないということになり， $(\star)$ は正しいです．

次に，外側のループが一つ進むごとに順列がどう変化しているかを見てみます．以下，例として $P=(0, 2, 3, 5, 4, 1)$ を用います．

N = 6
P = [0, 2, 3, 5, 4, 1]

def swap(i):
    j = (i + P[i]) % N
    P[i], P[j] = P[j], P[i]

for i in range(N):
    for _ in range(N - 1):
        swap(N - i - 1)
    print(P)

外側のループ毎に順列の状態を出力するコードです．以下に出力を示します．

[1, 2, 3, 5, 4, 0]
[2, 3, 4, 5, 0, 1]
[3, 4, 5, 0, 1, 2]
[4, 5, 0, 1, 2, 3]
[5, 0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]

$i$ 回目のループが終了した時点で， $P _ {N-i-1+j} = j\;(j=0,\ldots,i)$ となっていそうです．これを以下の 2 ステップに分けて示します．

$i=0$ の場合に正しいこと
$i=l-1\geq 0$ の場合に正しいと仮定すると， $i=l$ の場合も正しいこと

$i=0$ の場合は， $(\star)$ より添え字 $k=N-1$ を $N-1$ 回連続して選択した後は必ず $P _ k = 0$ となっていることから従います．

$i=l-1\geq 0$ の場合に正しいことを仮定すると， $P _ {N-l+j} = j\;(j=0,\ldots,l-1)$ です．

添え字 $k=N-l-1$ を連続して選択した場合に，swap 相手の添え字が初めて $k$ より大きくなるタイミングを考えます．仮定より， $P _ {m} \in \{0,\ldots,l-1\}$ を満たす全ての $m$ に対して $k\lt m$ が成立します．従って，これは $P _ k = l$ となったタイミングに限られます．そして，

$P _ k = l$ となるまでは $P _ k \lt l$ となりえないこと
$(\star)$ の性質

の 2 つから， $P _ k = l$ となるまでの最大の操作回数は $N-l-1$ 回で上から抑えることが出来ます．更に， $P _ k = l$ となった直後の $l$ 回の操作で $P _ {N-l-1+j} = j\;(j=0,\ldots,l)$ となることから， $i=l$ の場合も正しいことが言えます．

以上より，冒頭に示した解法は正当であることが言えました．