きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 103 : D - Islands War

問題

D - Islands War

N 個の島と島 i と島 i+1 を結ぶ橋 i が N - 1 本ある.また,島 a_i と b_i を行き来できなくしたいという島の住民からの要望が M 個ある.この時,最小でいくつの橋を無くせば M 個の要望すべてに対応できるかを求める問題.1 <= N, M <= 10^5.

解法

島 1 から見ていく.ここで,島 1 と行き来できなくしたい島の番号を set に入れておくなどしておく.もし,この set の中に島 2 が入っているならばこの橋は無くすべき橋.入っていなければこのまま残しておいてよい橋と判定できる.橋を残した場合は,set に島 2 と行き来できなくしたい島の番号を set に追加する.橋を無くした場合は,set の中身を clear し,次の島と行き来できなくしたい島の番号を set に入れればよい.これを島 N まで続けていけばよい.計算量は O(N + M) になり,解説に載っていた想定解よりちょっと早い?(そうでもないか)

解答

Submission #3002302 - AtCoder Beginner Contest 103

f:id:babcs2035:20180813203653p:plain

gist.github.com