CodeChef May Challenge 2020 - Triple Sort

• 問題
• AC

3つの数のシフト操作は2つの互換でできていて、つまり偶置換なので、与えられた置換が奇置換だとどうやっても$1, 2, ..., N$に戻すことはできない。

偶置換の場合について具体的な手順を与えるために、与えられた置換を巡回置換に分解して考える。長さ$k(\ge 3)$の巡回置換$(p_1 p_2 ... p_k)$があるとき、$p_1, p_2, p_3$に操作を適用すると先頭の2つが正しい場所に収まって長さ$k-2$の巡回置換$(p_3 ... p_k)$が残る。$k=3$の場合はこの操作ですべての数が正しい場所に戻るので、結局$k$が奇数ならこの操作を最後まで繰り返せることになる。いっぽう$k$が偶数の場合は、長さ$2$の巡回置換、つまり互換が残るので、これらの処理を考える。2組の互換$(p_1 p_2), (p_3 p_4)$がある時、操作$p_1, p_2, p_3$と$p_2, p_3, p_4$を順に適用することで、4つの数がすべて正しい位置に戻る。こうして2組ずつ処理していったとき、偶置換であれば最後に端（=1つの互換）が残ることもないので、けっきょく常に$1, 2, ..., N$に戻せることになる。また、操作1回につき2つの数を正しい位置に戻せるので、操作回数の上限も満たせることがわかる。