Kazun の競プロ記録

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

AtCoder Beginner Contest 248 F問題 Keep Connect

AtCoder ABC ABC248 F問題 500 pts

問題

提出解答

問題の概要

無向グラフ $G=(V,E)$ を以下で定義する.

$V=\{1,2, \dots, N\} \coprod \{1', 2', \dots, N'\}$
$E=\{(i, i+1) \mid 1 \leq i \lt N\} \coprod \{(i', (i+1)') \mid 1 \leq i \lt N\} \coprod \{(i, i') \mid 1 \leq i \leq N\}$

$k=1,2, \dots, N-1$ それぞれに対して, 次を満たす $G$ の全域部分グラフ $H=(V, F)$ の個数を求め, $P$ で割った余りを求めよ.

$|E \setminus F|=k$
$H$ は連結

制約

$2 \leq N \leq 3000$
$9 \times 10^8 \leq P \leq 10^9$
$P$ は素数

解法

以降では説明のために, $(3N-2)$ 本の辺をそれぞれ

$e_i=(i,i+1)$
$f_i=(i', (i+1)')$
$g_i=(i, i')$

と名付けることにする.

動的計画法で解くことにする. $1 \leq i \leq N, 1 \leq k \leq N, \alpha \in \{A,B\}$ に対して, ${\rm DP}[i,k,\alpha ]$ を以下を満たす場合の数で定義する.

考えるグラフをのから生成される部分グラフに制限したとき, 取り除かれた辺の本数がで,
- $\alpha=A$ のとき: 連結であるような全域部分グラフの数
- $\alpha=B$ のとき: 連結成分がちょうど2つであり, $i, i'$ が非連結であるような全域部分グラフの数.

ベースケースを考える. 今回のベースケースは $i=1$ のときであり, この場合に考えるべき辺は $g_1$ のみである. これらを残すか残さないかどうかで考えることにより,

${\rm DP}[1,k,\alpha]=\begin{cases} 1 & ( (k,\alpha)=(0,A) \lor (k,\alpha)=(1, B) ) \\ 0 & ({\rm otherwise}) \end{cases}$

である.

更新式を考える. $(i-1)$ まで決定している状況で $i$ の状況を決定づけるためには, 新たに $e_{i-1}, f_{i-1}, g_i$ を残すかどうかの判定をすればよい. このとき, 以下の表を利用することにより, 遷移がを求めることができる (ただし, 青数字は $e_{i-1}, f_{i-1}, g_i$ のうち,残さなかった辺の数を表す).

ABC 248 F 遷移図

このとき, 答えは ${\rm DP}[N,k,A]$ である. 配列の要素数は $O(N^2)$ で, 各要素の更新は定数時間でできるので, 全体の計算量は $O(N^2)$ である.