人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder Beginner Contest 129:D - Lamp

問題

atcoder.jp

解法

各行・列について障害物がある x, y 座標をソートして配列に持っておく.これを前処理として行っておく.

各マスについて,そのマスから見て上下左右の最も近い障害物の座標は,前処理で求めておいた配列上で二分探索をすることで求めることができる.各マスについてかかる計算量は O(log(H + W)) なので全体で O(HW log(H + W)).

解答

atcoder.jp

f:id:babcs2035:20190615142519p:plain