AtCoder Beginner Contest 233 F 問題 Swap and Sort

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の並び替え $(P_1, \dots, P_N)$ が与えられる. 以下の操作を $5 \times 10^5$ 回以下行って, $(P_1, \dots, P_N)=(1, \dots, N)$ にできるか?

$1 \leq i \leq M$ となる整数 $i$ を選び, $P_{a_i}, P_{b_i}$ を入れ替える.

可能ならばその一例をあげ, 不可能ならばその旨を報告せよ.

制約

この問題は以下の問題と同じである.

$[\![N]\!]$ を $N$ 以下の整数全体の集合とする. $E=\{a_j b_j \mid j=1,2, \dots, M\}$ として, 無向グラフ $G=([\![N]\!] , E)$ と $(1, \dots, N)$ の並び替え $(P_1, \dots, P_N)$ が与えられる.

以下の操作を $5 \times 10^5$ 回以下で $(P_1, \dots, P_N)=(1, \dots, N)$ にできるか: 辺 $e \in E$ を選び, 端点を $a,b$ とする. $P_a, P_b$ を入れ替える.

このとき, 操作が可能であることの必要十分条件は

無向グラフ $G$ において, 任意の $i=1,2, \dots, N$ に対して, 頂点 $i,P_i$ が同じ連結成分にある.

である. 以下ではこのことを示す.

ある $i=1,2, \dots, N$ において, 頂点 $i,P_i$ が同じ連結成分にないときは $P_i=i$ とすることが不可能である.

条件を満たす時は可能であることを示す. 以下のことを示す.

連結な $n$ 頂点のグラフ $H=(W,B)$ において, $\dfrac{n(n-1)}{2}$ 回以下の操作で要求を満たすようにできる.

これが構成的に示すことができれば, 各連結成分ごとにその方法を行うことで, 一例を作ることができる.

$H$ の全域木 $F=(W, B')$ を1つ選び, それを固定する. この $F$ 上で可能であることを示す.

$n=1$ のときは明らかに $0$ 手で可能である.

$n \geq 2$ とし, 頂点数が $n$ 未満の連結グラフにおいては必ず成立すると仮定する. ここで, $F$ は全域森なので, 葉 $v \in V$ が存在する. そして, $w \in V$ を $v=P_w$ となるように取る. ここで, 仮定から, $v,w$ は同じ連結成分の頂点なので, $v,w$ を端点とするパス $Q: v=q_0,q_1, \dots, q_m=w$ が存在する. このとき, $Q$ はパスなので, 長さ $m$ は $n-1$ 以下である *1. そして, 辺 $q_{m-1}q_m, q_{m-2}q_{m-1}, \dots, q_1q_2, q_0q_1$ の順に操作することにより, $P_v=v$ とすることができる.

よって, $F-v$ の場合に帰着でき, $v$ は葉なので, $F-v$ も連結である. 従って, 仮定から, $\dfrac{(n-1)(n-2)}{2}$ 回以下で $E'-\{v\}$ に対して要求を満たすことができる. 従って, 合わせて

$\dfrac{(n-1)(n-2)}{2}+m \leq \dfrac{(n-1)(n-2)}{2}+(n-1)=\dfrac{n(n-1)}{2}$

回以下の操作で完成できることを示すことができた.

以上の証明をそのまま実装することにより, 一例を作ることができた. 操作回数について, $x+y=z, x,y \geq 0$ という状況下において, $\dfrac{x(x-1)}{2}+\dfrac{y(y-1)}{2} \leq \dfrac{z(z-1)}{2}$ という不等式が成り立つことから, 操作回数は高々 $\dfrac{N(N-1)}{2}$ 回以下であり, $N \leq 1000$ より, $\dfrac{N(N-1)}{2} \leq 499500 \leq 5 \times 10^5$ である.