AtCoder Grand Contest 058 A問題 Make it Zigzag
問題
提出解答
問題の概要
の順列
が与えられる.
回以上
回以下の隣接項同士の入れ替えで以下の条件を満たすようなものを1つ例示せよ.
に対して,
に対して,
制約
は
の並び替え
解法
次のようにすればよい.
ならば
を入れ替える.
の順に以下を実行する. なお, これまでの操作により
が保証されている.
ならば,
を入れ替える.
ならば何もしない.
のとき
ならば,
を入れ替える.
- そうでなければ,
を入れ替える.
ならば,
を入れ替える.
これが条件を満たすことの理由は以下である.
の各ステップが終わったあと,
となっている.
の各ステップにおいて入れ替えは高々1回である. また, 最初で行う入れ替えも高々1回なので, 合計でも高々
回である.
なお, の各ステップにおいて,
の入れ替えをするか,
の入れ替えをするか, 何もしないかを選ぶ方法については場合わけの代わりに, 実際にシミュレーションで調べても良い.