Kazun の競プロ記録

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

AtCoder Beginner Contest 281 G問題 Farthest City

AtCoder ABC281 ABC G問題 600 pts

問題

提出解答

問題の概要

$N$ 個の頂点 $1,2, \dots, N$ からなる単純無向グラフのうち, 以下を満たすようなものの数を ( $M$ で割った余り) を求めよ.

連結であり, $u=2,3, \dots, N-1$ において, $\operatorname{dist}(1,u) \lt \operatorname{dist}(1,N)$ である.

制約

$1 \leq N \leq 500$
$10^8 \leq M \leq 10^9$

解法

次のことが成り立つことを利用する.

無向連結グラフ $G=(V,E)$ において, $u \in V, vw \in E$ とする. このとき, $\left|\operatorname{dist}(u,v)-\operatorname{dist}(v,w) \right| \leq 1$ が成り立つ.

$V=\{1,2, \dots, N\}$ とする. $v \in V$ に対して, $\operatorname{dist}(1,v)=d_v$ が成り立つような単純連結グラフは次のようにして漏れなく重複無く作ることができる. なお, $\operatorname{dist}(1,v)=d$ を満たす $v \in V$ の個数を $k_d$ と書くことにする.

の順に以下のようにする.
- $d_v=d$ となる全ての $v \in V$ に対して, $d_u=d-1$ となる $u$ を $1$ つ以上選び, その選んだ $u$ に対して, 辺 $uv$ を追加する.
- $d_v=d_w=d$ となる $v,w \in V, v \neq w$ の組 $(v,w)$ を $0$ 個以上選び, 辺 $vw$ を追加する.

このとき, $(d-1)$ まで確定させている状態から $d$ を確定させるとき, 距離が $d$ 以下である頂点の数と距離がちょうど $d$ である頂点の数さえわかればよいことがわかる.

このことから, 次のような動的計画法で求めることにする.

${\rm DP}[r,k$ ] : 距離が $d$ 以下の頂点数が $r$ 個, 距離がちょうど $d$ である頂点数が $k$ であり, $r$ 個の頂点が連結であるようなグラフの数.

ベースケースは頂点 $1$ との距離を述べているので, ${\rm DP}[1,k$ =[k=1] ] である.

更新式は上で述べたことから, 配る DP の形で,

${\rm DP}[r+k, k] \xleftarrow{{\rm add}} \dbinom{N-1-r}{k} (2^l-1)^k 2^{k(k-1)/2} {\rm DP}[r,l] \quad (0 \leq r, 0 \leq k, r+k \leq N, l \leq r)$

となる.

なお, 各係数の意味は以下の通りである. なお, 距離が $d$ より大きい頂点が $r$ 個であるとする.

$\dbinom{N-1-r}{k}$ : 距離が $d$ より大きい, 頂点 $N$ 以外の $(N-1-r)$ 個の頂点から $k$ 個選ぶ方法.
$(2^l-1)^k$ : 上で選んだ $k$ 個の頂点それぞれについて, 距離が $d$ である $l$ 個の頂点から1つ以上の頂点を選び, 辺で結ぶ方法
$2^{k(k-1)/2}$ : 選んだ $k$ 個の距離が $d$ である頂点同士を結ぶ方法.

このとき, 最終解答は頂点 $N$ が最遠点にならなくてはならないので, 上で述べた考え方を再利用して,

$\displaystyle \sum_{k=1}^{N-2} {\rm DP}[N-1,k] (2^k-1)$

である.

計算量は, 動的計画法における要素数が $O(N^2)$ 個, 更新式が各要素に対して $O(N)$ 時間であるから, 全体で $O(N^3)$ 時間になる.