Kazun の競プロ記録

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

AtCoder Beginner Contest 299 E問題 Nearest Black Vertex

AtCoder ABC ABC299 E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純連結無効グラフ $G=(V,E)$ がある. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

である.

各頂点を白か黒かで塗る方法のうち, 次の条件を満たすような塗り方は存在するか? 存在するならば, その一例を求めよ.

$1$ 個以上の頂点は黒で塗られている.
$k=1,2, \dots, K$ に対して, 次が成り立つ: 頂点 $p_i$ と「黒で塗られた頂点のうち頂点 $p_i$ からの距離が最小である頂点」の距離がちょうど $d_i$ である.

制約

$1 \leq N \leq 2000$
$N-1 \leq M \leq \min \left(\dfrac{N(N-1)}{2}, 2000 \right)$
$1 \leq u_j, v_j \leq N$
$G$ は連結である.
$0 \leq K \leq N$
$1 \leq p_1 \lt \dots \lt p_K \leq N$
$0 \leq d_k \leq N$

解法

今回の問題の制約から, 各 $u,v \in V$ に対して, $G$ 上の $u,v$ 間距離 $\operatorname{dist}(u,v)$ を BFS によって $O(N(N+M))$ 時間の前計算によって, $O(1)$ 時間で取得可能であるので, この前計算をしておく.

ここで, 各 $k=1,2, \dots, K$ に対して, 頂点 $p_k$ から $d_k$ 未満であるような頂点は白でなければならないので, 白で確定させておく.

そして, 色が未確定の頂点については　「黒で塗った頂点のうち, ... であるような頂点が存在する」という形の条件の集まりなので, 未確定の頂点を全て黒で塗るのが最適である.

よって, このような塗り方において, 各 $k=1,2, \dots, K$ に対して条件を満たすかどうかを確認すればよい.

また, $k=1,2, \dots, K$ に対して全て条件成立のとき,

$K=0$ の場合は白確定の頂点が存在しないので, 全て黒の頂点になる. そして, $N \geq 1$ である.
$K \gt 0$ の場合, 頂点 $p_1$ からの距離が $d_1$ であるような頂点で, 黒である頂点が存在する.

よって, 黒で塗った頂点が存在する.

この方針により, $O(N(N+M))$ 時間で判定及び構築ができた.