Kazun の競プロ記録

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

AtCoder Beginner Contest 291 F問題 Teleporter and Closed off

AtCoder ABC291 ABC 500 pts F問題

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

問題

提出解答

問題の概要

有向グラフ $D=(V,A)$ がある. ここで,

$V=\{1, 2, \dots, N\}$

である. また, 有向辺については次のようになっている.

$\overrightarrow{ij} \in A \iff 1 \leq j-i \leq M$ かつ $S_i$ の $(j-i)$ 文字目が $\texttt{1}$

このとき, $k=2,3, \dots, N-1$ において, $D-k$ は頂点 $1$ から頂点 $N$ へ到達可能か? 可能ならば頂点 $1, N$ 間の距離を求めよ.

ここで, $D-k$ とは $D$ から頂点 $k$ 及び $k$ から出る辺と $k$ に入る辺を全て取り除いた有向グラフである.

制約

$3 \leq N \leq 10^5$
$1 \leq M \leq 10$
$M \lt N$
$S_i$ は $\texttt{0}, \texttt{1}$ からなる長さ $M$ の文字列
$i+j \gt N$ ならば, $S_i$ の $j$ 文字目は [\texttt{0}] である.

解法

$N \geq 3$ であるので, $D-k$ において, 頂点 $1$ から頂点 $N$ へ到達可能ならば, 距離は $1$ 以上である. よって, 有向辺を $1$ つ以上利用することになる.

よって, どの有向辺を利用するかで場合分けする. ここで, $\overrightarrow{ij} \in A$ を使う移動の方法については $i \lt k \lt j$ となる $k$ における, $D-k$ 上での移動の方法に有効である.

$\overrightarrow{ij} \in A$ を使う場合における $D-k$ における頂点 $1$ から頂点 $N$ への移動の方法は

頂点 $1$ から頂点 $i$ へ.
$\overrightarrow{ij} \in A$ .
頂点 $j$ から頂点 $N$ へ.

である. 上と下のパートについてはそれぞれ最短距離で移動すればよく, 独立に選ぶことができる.

よって, $\overrightarrow{ij} \in A$ を経由する場合における $D-k$ 上の頂点 $1$ から頂点 $N$ への辺の本数の最小値は

$\operatorname{dist}_D(1,i)+1+\operatorname{dist}_D(j,N)$

である.

これを全ての辺について動かすことにより,

$\displaystyle \operatorname{dist}_{D-k}(1,N)=\min_{\substack{\overrightarrow{ij} \in A \\ i \lt k \lt j} } \left( \operatorname{dist}_D(1,i)+\operatorname{dist}_D(j,N) \right)+1$

となる.

ここで, $\operatorname{dist}_D(1,i)$ は頂点 $1$ から始める $D$ の BFS, $\operatorname{dist}_D(j,N)$ は $D$ の辺を全て反転させた有向グラフ $D'$ における頂点 $N$ からの BFS で共に $O(N)$ 時間で求めることができる.

そして, $\overrightarrow{ij} \in A, i \lt k \lt j$ となる $(i,j,k)$ の個数は高々 $NM^2$ 個である. よって, $O(NM^2)$ 時間で求めることができた.