制約:マス数H×Wに10^5などの制約のある問題
AtCoder
JOI
JOIG
JOI難易度7
差分更新
連結成分
Union-Find
二次元グリッド
制約:マス数H×Wに10^5などの制約のある問題
【問題集】平面走査
平面走査
平面走査:連結性を管理する
累積和テク:左右両端からの累積和や累積結果を前処理
累積和
前処理
累積和テク:累積和や累積結果を前処理しておく
UnionFind を使って、差分更新を頑張る！ UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います！ 問題へのリンク 問題概要 のグリッドがあって…
得点差最大化ゲーム
ゲーム
AtCoder
JOI
JOIG
JOI難易度6
二次元グリッド
0と1の問題
縦方向と横方向の情報を整理する
前処理
差分更新
制約条件:総和=K
操作
操作:flip
ゼロサムゲーム
制約:マス数H×Wに10^5などの制約のある問題
データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…
