AtCoder Regular Contest 144 C - K Derangement
解けなかったので、こういう流れで解きたかったという妄想を書きます
分かりやすさのために、以降i=0~N-1で0~N-1の順列を並び替える問題として考えます
解説
問題文で問われているのは辞書順最小なので、先頭からなるべく小さい数を入れていきたいです。
上のグラフは横軸がiの値、縦軸がAiの値で、赤線が理想の配置です
i=0~K-1の時は Aiにi+K以上の値しか使えないため、Ai = i+kとするのが理想で
i=K~2K-1の時はAiにi-Kも使えるようになるので、Ai = i-Kとするのが理想です
i = 2K ~ N-1以上の時は、Aiとして使える値も2K~N-1であり
両方から2Kを引けば上と同じ問題に帰着できます
よって、理想の配置は0~2N-1を順に並べた上で
2K個ずつのブロックに分け、各ブロックごとに前K個と後ろK個を入れ替えたような形になっています。
例えばN = 12, K = 3なら
3, 4, 5, 0, 1, 2, 9, 10, 11, 6, 7, 8
が答えで、上の説明の通りの並びになっています
(0-indexdで書いたので、値が1ずつ小さいことに注意)
Nが2Kで割り切れるなら上の理想形が作れますが、割り切れない場合の考察も必要です。
割り切れない場合、一番後ろに2K個未満のブロックが生まれてしまいますが、そのブロックの中だけでうまく並び替えて解を作ることはできません。
なぜなら後ろのK個は、K個以上前に移動させないといけませんが
今見ているブロックにその余裕は無いからです。
よって前のブロックにはみ出る必要があり、後ろの2K個について
後ろのK個を前に持っていき、前のK個を小さい順に並び替えて後ろに持ってくのが最適です(これは必ず成功します)
(入れ替え前)
(入れ替え後)
(ちなみにこれと同じ考察からN/2<Kの時に解がないことが分かります)
