Kazun の競プロ記録

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

AtCoder Beginner Contest 289 E問題 Swap Places

AtCoder ABC289 ABC 500 pts E問題

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

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ がある. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

である. また, 各頂点 $i \in V$ について, $C_i=0$ ならば赤, $C_i=1$ ならば青で頂点 $i$ は塗られている.

最初, 高橋くんは頂点 $1$ に, 青木くんは頂点 $N$ にいる.

次の行動を繰り返し行うことにより, 高橋くんが頂点 $N$ に, 青木くんが頂点 $1$ にいる状態にすることは可能か? 可能ならばその行動回数の最小値を求めよ.

2人は同時に各人が今いる頂点の近傍の頂点を選び, その頂点へ移動する. ただし, 2人の移動先の頂点の色は異なっていなければならない.

$T$ 個のマルチケース

制約

$1 \leq T \leq 1000$
$2 \leq N \leq 2000$
$1 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2000 \right)$
$C_i \in \{0,1\}$
$1 \leq u_i, v_i \leq N$
$G$ は単純無向グラフ
$T$ 個のケースにおける $N$ の総和は $2000$ 以下
$T$ 個のケースにおける $M$ の総和は $2000$ 以下

解法

$G$ に対して, $V \times V$ と頂点に持つ, 次のような有向グラフ $H=(V \times V, A$ を構成する.

$A$ は以下を満たすような $\overrightarrow{(x,y)(z,w)}$ 全体の集合とする.

高橋くんが $x$ , 青木くんが $y$ にいる状態から1回の移動で高橋くんが頂点 $z$ , 青木くんが頂点 $w$ にいる状態にすることが可能である.

$H$ の頂点数は $N^2$ である. 辺の数を $M'$ とすると,

$\displaystyle \begin{align*} M' &\leq \sum_{u \in V} \sum_{v \in V} \operatorname{deg}(u) \operatorname{deg}(v) \\ &=\left(\sum_{u \in V} \operatorname{deg}(u) \right)\left(\sum_{v \in V} \operatorname{deg}(v) \right) \\ &=\left(\sum_{u \in V} \operatorname{deg}(u) \right)^2 \\ &=(2M)^2 \\ &=4M^2 \end{align*}$

となり, $M' \leq 4M^2$ である. 今, $M \leq 2000$ であることから, $G$ から直接 $H$ を構成しても問題ない.

$H$ の構成方法から, 以下は同値である.

高橋くんが頂点 $N$ に, 青木くんが頂点 $1$ にいる状態にすることは可能
$H$ において, 頂点 $(1,N)$ から頂点 $(N,1)$ へ到達可能である.

また, 頂点 $(1,N)$ から頂点 $(N,1)$ への有向歩道と2人の移動の方法が1対1に対応することから, 移動の最小回数は $H$ における $(1,N)$ から $(N,1)$ 間の距離と一致する.

これは $H$ におけるBFS によって求めることができる.

よって, $H$ の構成及び探索合わせて $O(N^2+M^2)$ 時間で求めることができた.