Kazun の競プロ記録

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

AtCoder Beginner Contest 271 E問題 Subsequence Path

AtCoder ABC271 ABC E問題 500 pts

問題

提出解答

問題の概要

重み付き有向グラフ $D=(V,A,W)$ が与えられる. なお,

$V:=\{1,2, \dots, N\}$
$A:=\{ \overrightarrow{A_j B_j} \mid 1 \leq j \leq M\}$
$W: A \to \mathbb{Z}; W \left(\overrightarrow{A_j B_j} \right)=C_j$

である. 次を満たす有向パス $P: a_{t_1} \dots a_{t_m}$ は存在するか? 存在するならばそのような有向パスのうち, 長さの総和の最小値を求めよ.

$P$ は $1$ を始点, $N$ を終点とする.
$(t_1, t_2, \dots, t_m)$ は $(E_1, \dots, E_K)$ の連続とは限らない部分列.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq M,K \leq 2 \times 10^5$
$1 \leq A_j, B_j \leq N$
$D$ に自己ループはない.
$1 \leq C_j \leq 10^9$
$1 \leq E_k \leq K$

解法

次のような動的計画法で解く.

${\rm DP}[k, v ]$ を $E$ を $(1,2, \dots, k)$ に制限した場合で, 終点が頂点 $j$ であるような有向パスの長さの総和の最小値 (存在しない場合は $+ \infty$ ).

このとき, ベースケースは $i=0$ のときで

${\rm DP}[0, v ]=\begin{cases} 0 & (v=1) \\ +\infty (v \neq 1) \end{cases}$

である.

更新式については有向辺 $\overrightarrow{A_{E_i} B_{E_i}}$ を採用するか否かで場合分けすることによって,

${\rm DP}[k, v ]=\begin{cases} \min \left({\rm DP}[k-1, B_{E_k}], {\rm DP}[k-1, A_{E_k}]+W \left(\overrightarrow{A_{E_k} B_{E_k}} \right) \right) & (v=B_k) \\ +\infty & (v \neq B_k) \end{cases}$

となる. このときの ${\rm DP}[K,N]$ が答えである.

しかし, これをそのまま計算しようとすると, 計算量が $O(N+KM)$ 時間/空間となり, 間に合わない.

ところが, 更新式をみてみると, ${\rm DP}[k, v$ ] を求めるとき, $v \neq B_{E_k}$ の場合は全て ${\rm DP}[k-1, v]$ である. よって, ほとんどは $(k-1)$ の時と同じであることがわかる. よって, ${\rm DP}[k, \bullet$ ] の計算結果を使い回すことによって, 各 $k$ に対する更新を $O(1)$ 時間で終了することができる.

このような計算結果の使い回しによって, 時間計算量, 空間計算量共に $O(N+M+K)$ 時間/ 空間で計算できる.