外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

線形時間の解法

trueryob ·

解説している問題 adjacent swap

一回のswap操作により、サイクルの個数は11増えるか11減ります。

よって、ある順列から任意の順列までの操作回数の偶奇を、サイクルの個数の差分から求めることができます。

順列のサイクル分解はO(N)O(N)で出来ます。

提出例