Kazun の競プロ記録

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

AtCoder Beginner Contest 277 C問題 Ladder Takahash

AtCoder ABC277 ABC C問題 300 pts

問題

提出解答

問題の概要

$N$ 本のハシゴがある $10^9$ 回建てのビルがある.

$j$ 番目のハシゴは $A_j$ 階と $B_j$ 階を結んでおり, $A_j$ 階から $B_j$ 階へ, または $B_j$ 階から $A_j$ 階へ移動することができる (※ 間の階は移動不可能).

高橋君は最初, $1$ 階にいる. $1$ 階以上のハシゴを利用することで, 最高何階までいけるか? ただし, 同じ階の移動は自由にできるが, ハシゴ以外の方法で別の階への移動はできない.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_j, B_j \leq 10^9$
$A_j \neq B_j$

解法

次のような無向グラフ $G:=(V,E)$ を作成する.

$V:=\{1,2, \dots, 10^9\}$
$E:=\{A_j B_j \mid j=1,2, \dots, N\}$

このとき, 高橋君が $x$ 階へ移動可能であることと, $G$ において頂点 [tex 1] と頂点 $x$ が連結であることは同値である.

しかし, $G$ は $10^9$ 頂点であるから, 全ての情報を持つことができない. だが, ハシゴが存在する階層は高々 $2N$ 個であるから, ハシゴがある階についてのみを着目すれば良い.

よって, $G$ の代わりに次の部分グラフ $H:=(W, F)$ を考えれば良いことになる.

$W:=\{x \mid \exists j ~{\rm s.t.}~x=A_j \lor x=B_j\}$
$F:=E$

この $H$ 上で頂点 $1$ から始まる BFS や DFS を行うことにより, $O(N)$ 時間で正解を導くことが出来る.