平面走査:連結性を管理する
見積り大事
二次元グリッド
迷路
BFS
連結成分
二次元グリッド上の壁に囲われた連結成分
壁マス
座標圧縮
橙色diff
AtCoder
AtCoder600点
ABC-G
平面走査:連結性を管理する
連結性に着目する
平面走査
NoviSteps4D
二次元平面上のN点の問題
高度典型
そのまま覚えたいシンプル設定の中堅以上の典型問題
方針を決めるのが大変な問題。 問題へのリンク 問題概要 二次元平面上の 個の格子点に碁石が置かれている。 このとき、碁石によって囲われている格子点の個数を求めよ。より正確には、「その空き格子点から上下左右の空き格子点への移動を繰り返して点 (-1, …
AtCoder
JOI
JOIG
JOI難易度7
データ構造テク：差分更新
連結成分
Union-Find
二次元グリッド
制約:マス数H×Wに10^5などの制約のある問題
【問題集】平面走査
平面走査
平面走査:連結性を管理する
累積和テク:左右両端からの累積和や累積結果を前処理
累積和
データ構造テク：前処理
累積和テク:累積和や累積結果を前処理しておく
NoviSteps1D
AOJ
UnionFind を使って、差分更新を頑張る！ UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います！ 問題へのリンク 問題概要 のグリッドがあって…
