Kazun の競プロ記録

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

AtCoder Regular Contest 147 B問題 Swap to Sort

AtCoder ARC147 ARC B問題 500 pts

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の順列 $P=(P_1, \dots, P_N)$ がある. 以下の操作を繰り返し行い, $P$ を昇順に並び替えたい.

操作 (A): $i=1,2, \dots, N-1$ を選び, $P_i, P_{i+1}$ を入れ替える.
操作 (B): $i=1,2, \dots, N-2$ を選び, $P_i, P_{i+2}$ を入れ替える.

このとき, 操作 (A) の回数が最小であり, 合計操作回数が $10^5$ 以下である操作の手順を1つ挙げよ.

制約

$2 \leq N \leq 400$
$P$ は $(1,2, \dots, N)$ の順列

解法

$P$ が順列であることから, 以下の2つの値は一致する. その値を $K$ とする.

$P$ の第奇数項目にある偶数の数
$P$ の第偶数項目にある奇数の数

このとき, 操作 (A) の最小回数は $K$ である.

$K$ 以上であること: 操作 (A) を1回行うと, 第奇数項目にある偶数の数は $1$ 減るか, そのままか, $1$ 増えるかのどれかである. よって, $K$ の状態から $0$ の状態にするためには最低でも $K$ 回必要なことがわかる.
以下であること: 次のようにして回で第奇数項目にある偶数の数をにすることができる.
- 奇数項目にある偶数を全て左 (項番号が小さい方) に移動させる (第 $1,3,\dots, 2K-1$ 項目が偶数になる).
- 偶数項目にある奇数を全て左 (項番号が小さい方) に移動させる (第 $2,4,\dots, 2K$ 項目が奇数になる).
- $i=1,2, \dots, K$ に対して, 操作 (A) によって, $P_{2i-1}, P_{2i}$ を入れ替える.

これによって, 奇数項目には奇数が, 偶数項目が偶数が並んでいる状態になる. これにより, 奇数項目, 偶数項目それぞれに関してバブルソートを施すと, 全体としても昇順に並ぶ.

操作回数について考える. 長さが $M$ の順列について, 隣接項同士の入れ替えにおいては高々 $\dfrac{1}{2}M(M-1)$ 回で任意の順列にすることができる. また, $K \leq \dfrac{N}{2}$ であるから, 操作回数は多く見積もっても,

$\displaystyle 2 \times \left(\dfrac{1}{2} \cdot \dfrac{N+1}{2} \cdot \dfrac{N-1}{2}+\dfrac{1}{2} \cdot \dfrac{N}{2} \cdot \dfrac{N-2}{2} \right)+\dfrac{N}{2}=\dfrac{2N^2-1}{4} \leq \dfrac{N^2}{2} \leq 8 \times 10^4$

であるから $10^5$ 回以下に操作回数を収めることができた.