Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Grand Contest 058 A問題 Make it Zigzag

AtCoder AGC AGC058 A問題 400 pts

問題

提出解答

問題の概要

$(1,2, \dots, 2N)$ の順列 $P=(P_1, \dots, P_{2N})$ が与えられる.

$0$ 回以上 $N$ 回以下の隣接項同士の入れ替えで以下の条件を満たすようなものを1つ例示せよ.

$i=1,3,5,\dots, 2N-1$ に対して, $P_i \lt P_{i+1}$
$i=2,4,6,\dots, 2N$ に対して, $P_i \gt P_{i+1}$

制約

$1 \leq N \leq 10^5$
$P$ は $(1,2, \dots, 2N)$ の並び替え

解法

次のようにすればよい.

$P_{1} \gt P_{2}$ ならば $P_1, P_2$ を入れ替える.
の順に以下を実行する. なお, これまでの操作によりが保証されている.
- $P_{i+1} \lt P_{i+2} \lt P_{i+3}$ ならば, $P_{i+1}, P_{i+2}$ を入れ替える.
- $P_{i+1} \gt P_{i+2} \lt P_{i+3}$ ならば何もしない.
- のとき
  - $P_{i+1} \lt P_{i+3} \lt P_{i+2}$ ならば, $P_{i+1}, P_{i+2}$ を入れ替える.
  - そうでなければ, $P_{i+2}, P_{i+3}$ を入れ替える.
- $P_{i+1} \gt P_{i+2} \gt P_{i+3}$ ならば, $P_{i+2}, P_{i+3}$ を入れ替える.

これが条件を満たすことの理由は以下である.

$i=1,3,5, \dots, 2N-3$ の各ステップが終わったあと, $P_i \lt P_{i+1} \gt P_{i+2} \lt P_{i+3}$ となっている.
$i=1,3,5, \dots, 2N-3$ の各ステップにおいて入れ替えは高々1回である. また, 最初で行う入れ替えも高々1回なので, 合計でも高々 $(N-1)+1=N$ 回である.

なお, $i=1,3,5, \dots, 2N-3$ の各ステップにおいて, $P_{i+1}, P_{i+2}$ の入れ替えをするか, $P_{i+2}, P_{i+3}$ の入れ替えをするか, 何もしないかを選ぶ方法については場合わけの代わりに, 実際にシミュレーションで調べても良い.