Kazun の競プロ記録

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

AtCoder Regular Contest 159 A問題 Copy and Paste Graph

AtCoder ARC ARC159 A問題 300 pts

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

問題

提出解答

問題の概要

$NK$ 頂点の有向グラフ $D=(V,E)$ がある. ただし,

$V:=\{ (s,v) \mid 1 \leq s \leq K, 1 \leq v \leq N\}$
$E:=\{ (s,v)(t,w) \mid 1 \leq s,t \leq K, 1 \leq v \leq N, A_{v,w}=1\}$

である. このとき, 以下の $Q$ 個の質問に答えよ.

$D$ において, $(s_q, v_q)$ から頂点 $(t_q, w_q)$ へ到達可能か? 到達可能ならば経路の長さの最小値を求めよ.

(※ 実際の問題では頂点は $1$ 以上 $NK$ 以下の整数として与えられる.)

制約

$1 \leq N \leq 100$
$1 \leq K \leq 10^9$
$A_{i,j} \in \{0,1\}$
$1 \leq Q \leq 100$
$1 \leq s_q, t_q \leq K$
$1 \leq v_q, w_q \leq N$
$(s_q, v_q) \neq (t_q, w_q)$

解法

$K=1$ の場合は Warshall-Floyd 法を利用して前計算することにより, 前計算 $O(N^3)$ 時間, 1クエリ当たり $O(1)$ 時間, 合計 $O(N^3+Q)$ 時間で解くことができる.

これ以降は $K \geq 2$ とする. $D$ の部分グラフ $D'$ を $D$ において, $\{(s,v) \in V \mid s \in {1,2}, 1 \leq v \leq N \}$ が生成する部分有向グラフとする.

このとき, 有向グラフ $D,D'$ における距離を $d,d'$ と書くことにする. このとき, $(s,v), (t,w) \in V$ において以下が従う.

$s=t$ ならば, $d( (s,v), (t,w) )=d'( (0,v), (1,w) )$ である.
$s \neq t$ ならば, $d( (s,v), (t,w) )=d( (0,v), (1,w) )$ である.

(証明) $D$ における $(s,v), (t,w)$ 間の最短距離を達成する有向パスを

$(s.v)=(u_0, x_0), (u_1, x_1), \dots, (u_{k-1}, x_{k-1}), (u_k, x_k)=(t,w)$

とする. このとき, 有向辺の存在は $x_{\bullet}$ のみによって決定されるので,

$(s.v), (s, x_1), \dots, (s, x_{k-1}), (t,w)$

も $D$ 上の有向パスである.

$s \neq t$ ならば, 頂点のグループの番号の対称性から, $s=0, t=1$ としてもよい. このとき, 上のパスは $D'$ 上の有向パスである.

従って,

$d( (s,v), (t,w) )=d'( (0,v), (1,w) )$

である.

$s=t$ の場合も $s=t=0$ とすればよい.

これにより, $2N$ 頂点間の最短経路問題に帰着できた. 従って, Warshall-Floyd 法を利用して前計算することにより, 前計算 $O(N^3)$ 時間, 1クエリ当たり $O(1)$ 時間, 合計 $O(N^3+Q)$ 時間で解くことができる.

なお, この解法は $K=1$ の場合も含んでいる.