Kazun の競プロ記録

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

AtCoder Beginner Contest 254 E問題 Small d and k

AtCoder ABC ABC254 E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺からなる単純無向グラフ $G=(V,E)$ がある. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{a_i b_i \mid i=1,2, \dots, M\}$

とする. なお, 各頂点の次数は $3$ 以下である.

次の $Q$ 個の質問に答えよ.

質問 $q$ : 頂点 $x_q$ からの距離が $k_q$ 以下であるような頂点全てにおける番号の総和を求めよ.

制約

$1 \leq N \leq 1.5 \times 10^5$
$0 \leq M \leq \min(\frac{N(N-1)}{2}, \frac{3}{2}N)$
$1 \leq a_i \lt b_i \leq N$
$G$ は単純無向グラフ.
$1 \leq Q \leq 1.5 \times 10^5$
$1 \leq x_q \leq N$
$0 \leq k_q \leq 3$

解法

$d$ を $N$ 個の頂点の次数の最大値とする. このとき, 次が成り立つ.

頂点 $v$ との距離がちょうど $k$ であるような頂点の数は $d^k$ 個以下である.

証明

$k=0$ のときは頂点 $v$ のみが条件を満たすので成り立つ.
$k-1$ のときに成り立つとする. $k$ のとき, $v$ との距離がちょうど $k$ であるような頂点 $w$ に対して, $vw$ 最短路における $w$ の直前に通る頂点に着目する. この頂点と $v$ との距離は $(k-1)$ であり, 各頂点の次数は $d$ 以下なので, 距離がちょうど $k$ の頂点は $d \times d^{k-1}=d^k$ 個以下となることが示せた.

今回の問題の制約では, $d \leq 3, k_q \leq 3$ であるから, 頂点 $x_q$ との距離が $k_q$ 以下であるような頂点の個数は

$d^0+\dots+d^{k_q} \leq d^0+d^1+d^2+d^3 \leq 3^0+3^1+3^2+3^3=1+3+9+27=40$

より, 高々 $40$ 個である.

よって, 条件を満たすような頂点の数は比較的小さいので, 各質問に対して, 頂点 $x_q$ を視点とする BFS を行なう. ただし, 距離がちょうど $k_q$ である頂点からの探索を行わないようにすると, $S:=40$ として, 1質問あたり $O(S)$ , 全体で $O(N+QS)$ で求めることができる.