Kazun の競プロ記録

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

AtCoder Regular Contest 161 A問題 A Make M

AtCoder ARC ARC161 A問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

長さが奇数である整数列 $S=(S\1, \dots, S_M)$ に対して, 以下を満たすとき, $S$ は M 型であるという.

$S_1 \lt S_2 \gt S_3 \lt S_4 \gt \dots \gt S_{N-3} \lt S_{N-2} \gt S_{N-1}$

$N$ を奇数とする. 長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる. $A$ を適切に並び替えることによって, M 型にすることは可能か?

制約

$1 \leq N \leq 2 \times 10^5$
$N$ は奇数である.
$1 \leq A_i \leq 10^9$

解法

以下は同値である.

$A$ を適切に並び替えると, M 型にすることができる.
$A$ を昇順に並び替えた列を $B=(B_1, \dots, B_N)$ とし, $K=\dfrac{N+1}{2}$ とすると,
$B_1 \lt B_{K+1} \gt B_2 \lt B_{K+2} \gt \dots \gt B_{K+K-2} \lt B_{K+1} \gt B_{K+K-1}$
が成り立つ.

(下) ならば (上) は明らかなので, (上) ならば (下) を証明する.

$A$ を並び替えることによって, $A$ は M 型であるとする. このとき, $A$ の奇数項目の最小値を $X$ とする.

このとき, $A$ の奇数項目に $X$ より大きい整数が, $A$ の偶数項目に $X$ より小さい整数が存在する場合, これら $2$ 項は交換しても M 型を保ったままである.

このようにすることで, $A$ の奇数項目は全て $X$ 以下, 偶数項目が全て $X$ 以上にすることができる.

また, このときの $A$ に含まれる $X$ については以下のうちのどちらかが成り立つ.

$A$ の奇数項目が全て $X$ で, $A$ の偶数項目は全て $X$ より大きい.
$A$ の奇数項目にある $X$ の数と $A$ の偶数項目にある $X$ の数 (要するに $A$ にある $X$ の数) が $(N-K)$ 個以下.

どちらの場合にしても, 奇数項目, 偶数項目それぞれ昇順に並び替えることによって, $A$ は (下) での操作の結果による並び替えになり, M 型にもなる.