Kazun の競プロ記録

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

AtCoder Beginner Contest 267 E問題 Erasing Vertices 2

AtCoder ABC267 ABC E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ が与えられる. ただし,

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

とする. また, 頂点 $i$ には整数 $A_i$ が書かれている.

次の操作を $N$ 回行う.

$G$ にある頂点 $x$ を一つ選ぶ. $G$ の $x$ における近傍にある頂点に書かれている整数の総和をコストとする. その後, $G$ を $G-x$ に置き換える.

$N$ 回の操作におけるコストの最大値を全体のコストとする. 取りうる全体のコストの最小値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq U_j, V_j \leq N$
$G$ は単純.

解法

全体のコストの定義から, 求めるべきはコストの最大値の最小値なので, 二分探索を利用することにする.

つまり, 整数 $X$ に対して, 次の問題を解くことにする.

全体のコストを $X$ 以下にできるか?

これは次のアルゴリズムによって判定できる.

$P_v$ を $v$ の近傍 $w$ における $A_w$ の総和とする.
$Q$ を空の Queue とする.
$Q$ に $P_v \leq X$ であるような $v$ を全て enqueue する.
以下をが空ではない限り行う.
- $Q$ を dequeue し, その頂点を $v$ とする.
- の (残っている) 近傍に対して, 以下を行う.
  - $P_w$ から $A_v$ を減らす.
  - $w$ が $Q$ に enqueue されたことがなく, $P_w \leq X$ ならば, $Q$ に $w$ を enqueue する.
全ての頂点を enqueue できれば肯定的結論, そうでなければ否定的結論.

また, 解答の自明な下界は $0$ , 自明な上界は $N \max A$ であるから, 正解を $O( (N+M) \log (N\max A) )$ 時間で求めることができた.

なお, 判定アルゴリズムを見てみると, 実は貪欲法で解くことができるがわかり, 時間計算量を $O( (N+M) \log (N+M))$ 時間に削減できる.