AtCoder Beginner Contest 103 : 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