Kazun の競プロ記録

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

AtCoder Beginner Contest 244 E問題 King Bombee

AtCoder ABC ABC244 E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E=\{U_j V_j \mid j=1,2, \dots, M\})$ が与えられる. 以下を満たす整数列 $A=(A_0, A_1, \dots, A_K)$ の数を求めよ.

$1 \leq A_i \leq N$
$A_0=S, A_K=T$
$A_i A_{i+1} \in E$
$A_0, A_1, \dots, A_K$ の中に $X (\neq S,T)$ がちょうど偶数回現れる.

制約

$1 \leq N,M,K \leq 2000$
$1 \leq S,T,X \leq N$
$X \neq S,T$
$1 \leq U_j \lt V_j \leq N$
$G$ は単純無向グラフ

解法

動的計画法で解く. ${\rm DP}[i,v,\sigma ]$ を

${\rm DP}[i,v, \sigma]:=A_0, A_1, \dots, A_i$ まで確定させ, $A_i=v$ であり, これまでに $X$ が ( $\sigma=0$ : 偶数, $\sigma=1$ : 奇数) 回登場する列の数

とする.

ベースケースは

${\rm DP}[0,v,\sigma]=[v=S \land \sigma=0]$

である (制約より, $\sigma=0$ である).

更新式は, $v \in V$ の近傍を $N_G(v)$ をしたとき,

$v=X$ のとき

$\displaystyle {\rm DP}[i, v, \sigma]=\sum_{u \in N_G(v)} {\rm DP}[i-1, u, 1-\sigma]$

$v \neq X$ のとき

$\displaystyle {\rm DP}[i, v, \sigma]=\sum_{u \in N_G(v)} {\rm DP}[i-1, u, \sigma]$

となる.

このとき, 求めるべき答えは ${\rm DP}[K, T, 0]$ であり, 時間計算量 $O(K(N+M))$ で求めることができる.