Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)

　Dまで。二時間近くあってE通せないのは悲しい。

コンテストへのリンク

コンテスト後のツイート

D (長さ%3,0の個数%3)でbeautifulかは決まるのでDP。だだし、一回も反応しないものはダメなので、後で引く（尺取り）。
E 必要条件で決まるものを決めた後、Aを置換に分解して当て嵌めていけば良いと思ったが上手く出来ず。

— titia (@titia_til) June 18, 2026

E. Permutation Commutation

　コンテスト後、落ち着いて考えたら自力でACできた。

　Functional Graphと見て、サイクルに分解する。

　たとえば、

A=[4, 5, 1, 3, 6, 2]

　を考えると、(1,4,3)と(2,5,6)というサイクルがある。

　これに対応するBは、(1番目, 4番目, 3番目)が(1,4,3),(4,3,1),(3,1,4)もしくは、(2,5,6),(5,6,2),(6,2,5)でなくてはならない。（2番目, 5番目, 6番目）も同様。

　ここまではコンテスト中に実験で分かっていた。i→A[i]とうつるとき、対応するいずれかのサイクルでindexを一つずらしたように入れなくてはいけない、と。

　しかし、さらにサイクル長に関して条件がありそうだとは思ったが、上手くまとまらなかった。

　実際は、同じサイクル長のものでないといけない。サイクル長3のものをサイクル長1のもので埋める……みたいなことができる気がして混乱してしまったが、こういうことができないと気付き、同じサイクル長のものしか使えないと分かった。

　なので、サイクル長で分類すればACできた。