AtCoder Beginner Contest 222 E 問題 Red and Blue Tree

問題

提出解答

問題の概要

$N$ 頂点からなる木がある. この木の $N-1$ 本の辺を赤または青で塗る. このとき, 以下を満たすような塗り方は何通りか?

(条件) $i=1,2, \dots, M-1$ の順に, 駒を頂点 $A_i$ から頂点 $A_{i+1}$ へ最短路で移動させる. $M-1$ 回の移動終了後, 赤の辺の総通過回数を $R$ , 青の辺の総通過回数を $B$ としたとき, $R-B=K$ である.

制約

$2 \leq N \leq 1000$
$2 \leq M \leq 100$
$|K| \leq 10^5$
$1 \leq A_i \leq N$
$1 \leq U_i, V_i \leq N$
与えられるグラフは木である.

解法

与えられるグラフを $T=(V,E)$ とする. $N-1$ 本の各辺 $e$ に対して, $X: E \to \{1,-1\}$ を

$X(e)=\begin{cases} 1 & (辺 e は赤) \\ -1 & (辺 e は青) \end{cases}$

とする. このとき, 求める条件は, $P_{u,v}$ で, $u,v$ パスにある辺の集合とすると,

$\displaystyle K=\sum_{i=1}^{M-1} \left( \sum_{e \in E} X(e) [e \in P_{A_i, A_{i+1}} ] \right)$

となる. ここで, シグマの交換を行い, 変形することにより, この条件は

$\displaystyle K=\sum_{e \in E} X(e) \left( \sum_{i=1}^{M-1} [e \in P_{A_i, A_{i+1}} ] \right)$

になる.

ここで, 各 $i$ について, $[e \in P_{A_i, A_{i+1}}$ ] については, BFS を行うことにより, 簡単に求めることができる. これを $i=1,2, \dots, M-1$ とすることにより,

$\displaystyle \alpha_e:=\sum_{i=1}^{M-1} [e \in P_{A_i, A_{i+1}} ]$

とおくと, $N-1$ 個の $e \in E$ における $\alpha_e$ をあわせて $O(NM)$ で求めることができる.

よって, 問題は以下のように帰着することができる.

非負整数 $\alpha_{e_1}, \dots, \alpha_{e_{N-1}}$ が与えられる. このとき, $i=1,2, \dots, N-1$ に対して, $X(e_i)$ を $1$ または $-1$ に割り当てる方法のうち,

$\displaystyle \sum_{i=1}^{N-1} X(e_i) \alpha_{e_i}=K$

を満たす割り当て方は何通りか?

$Y: E \to \{0,1\}$ を $Y(e):=\dfrac{X(e)+1}{2}$ とする. このとき, $X(e)=2Y(e)-1$ なので,

$\displaystyle \sum_{i=1}^{N-1} X(e_i) \alpha_{e_i}=K \iff \sum_{i=1}^{N-1} Y(e_i) \alpha_{e_i}=\dfrac{1}{2} \left(K+\sum_{i=1}^{N-1} \alpha_{e_i} \right)$

になる. これはまさしく部分和問題である. この部分和問題は動的計画法により, 計算量 $O(N(NM+|K|))$ で求めることができる. ただし, 右辺が整数にならない場合や, 負の場合は, 動的計画法を経由せずに, $0$ と答えなければならない.

以上から, 全体の計算量 $O(N(NM+|K|))$ で解答を求めることができた.

Kazun の競プロ記録

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

AtCoder Beginner Contest 222 E 問題 Red and Blue Tree

問題

提出解答

問題の概要

制約

解法