Kazun の競プロ記録

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

AtCoder Beginner Contest 244 F問題 Shortest Good Path

AtCoder ABC ABC244 F問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向連結グラフ $G=(V=[\![N]\!], E=\{u_j v_j \mid j=1,2, \dots, M\}$ が与えられる.

$0,1$ からなる長さ $N$ の列に対して, 以下を満たすような列 $P=(P_1, \dots, P_k)$ のうち, $k$ の最小値を $\rho(S)$ と書くことにする.

$1 \leq P_i \leq N$
$P_i P_{i+1} \in E$
$S_i=0$ ならば, $P_1, \dots, P_k$ の中に $i$ が偶数回登場する.
$S_i=1$ ならば, $P_1, \dots, P_k$ の中に $i$ が奇数回登場する.

考えられる $2^N$ 通りの $S$ 全てにおける $\rho(S)$ の総和を求めよ.

ただし, 任意の $S$ に対して, 上の条件を満たす $P$ は必ず存在する.

制約

$2 \leq N \leq 17$
$N-1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq u_i,v_i \leq N$
$G$ は単純無向連結グラフ

解法

$0,1$ からなる長さ $N$ の列 $T$ と, $1$ 以上 $N$ 以下の整数 $k$ に対して, $\beta(T,k)$ で $T$ の $k$ 番目の要素の $0,1$ を入れ替えた列とする.

ここで, 次のような無向グラフ $H=(W,F)$ を考える.

$W:=2^V \times V$
$F:=\{(S,u)(\beta(S,v),v) \mid S \subset V, uv \in E \}$

このとき, $W$ における $(\beta(\boldsymbol{0}, x) , x)$ から $(S,y)$ へのパス $(S_1, x_1), \dots, (S_k, x_k)$ について, $x_1, \dots, x_k$ というパスが $G$ には存在し, しかもこのパスにおける各頂点の登場回数が $S_k=S$ になる.

逆に, 空でないパスに対して, 上のようにして, $x \in V$ を始点, $y \in V$ を終点とし, 状態が $S$ であるようなパスを求めることができる.

また, 空のパスにおいては明らかに $S=\boldsymbol{0}$ となる.

以上から, $S \neq \boldsymbol{0}$ に対して,

$\displaystyle \rho(S)=\min_{x,y \in V} (\operatorname{dist}_H ( ( (\beta(\boldsymbol{0}, x), x) , (S,y))+1)$

となることがわかる.

ここで, 各 $(S,y) \in W$ を固定したとき, $\displaystyle \tau(S,y):=\min_{x \in V} (\operatorname{dist}_H ( ( (\beta(\boldsymbol{0}, x), x) , (S,y))+1)$ は多点始点 BFS によって求める事ができる.

多点始点 BFS を使うので, 無向グラフ $H$ の位数とサイズを求める.

位数: $|W|=\left|2^{V} \times V \right|=N \times 2^N$
サイズ: $|F| \leq N^2 2^N$

である. よって, 多点始点 BFS を時間計算量 $O(N^2 2^N)$ で実行でき,

$\displaystyle \sum_{S \neq \boldsymbol{0}} \min_{y \in V} \tau(S,y)$

が解答になる.