AtCoder Beginner Contest 254 C問題 K Swap
問題
提出解答
問題の概要
長さが の整数列
がある.
この列に対して, 以下の操作を0回以上行い, を昇順に並び替えることができるか?
以上
以下の整数
を選び,
と
を入れ替える.
制約
解法
以下では数列の添字を1ずつ減らして 0-indexed であるとする.
まず, 次のことが成り立つ.
長さが の列
がある. 以下は同値である.
は
のある並び替えである.
に対して, 以下の操作を
回以上行い,
を
と一致させることができる.
-
以上
未満の整数
を選び,
と
を入れ替える.
-
ここで, 個の列
を次のように定める.
このとき, と
を入れ替えるということは ,
を
で割った商と余りを
としたとき,
の第
項目と第
項目を入れ替えることに対応する.
つまり, 上で述べた事実から, このことがわかる.
において,
で割った余りが等しい項目同士は自由に並び替えることができる.
このことから, を昇順に並び替えた列を
とし,
を昇順に並び替えた列を
と書くとき,
を昇順にすることができるための必要十分条件は
である.
計算量は を求めるためのソートがボトルネックになり,
で計算できる.