制約条件:正方形領域
AtCoder
AtCoder525点
ABC-F
青色diff
二次元平面上のN点の問題
制約条件:正方形領域
二分探索
二分探索:最適化問題を判定問題に帰着する
操作
操作をK回まで行える
最大スコア
操作:点を移動する
中央値(メディアン)に関する問題
絶対値やminを扱う問題
区分線形関数
全部混ぜて解く
そのまま覚えたいシンプル設定の中堅以上の典型問題
x軸とy軸について独立に考えてよい
Greedy:各要素について独立に考えてよい
Greedy
最適化問題
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
AtCoder
ABC-E
水色diff
二次元グリッド
グリッド上のDP
DP
二次元累積和
累積和
二分探索
【問題集】累積和・二分探索法・しゃくとり法
典型要素を詰め合わせた教育的問題
0と1の問題
制約条件:正方形領域
数え上げ問題
解空間:O(N^2)通りの選択肢
極大なものを考える
sparseな問題
ある量を固定して考える
そのまま覚えたい典型問題
単調性に着目する
累積和テク:区間の総和を累積和で高速に求める
【問題集】累積和
【問題集】二次元累積和
【問題集】累積和・いもす法
AtCoder475点
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
数え上げ問題
パリティ
DP
木DP
ヒストグラム
二次元グリッド
AtCoder
AtCoder1100点
AGC-D
再帰的構造に着目する
橙色diff
制約条件:正方形領域
制約条件:各グループの何かが等しい
解空間:O(2^N)通りの選択肢
市松模様・塗り分け
0と1の問題
なんか yukicoder で書いた問題に前半は似てた。でもこの問題の難しいところは後半の方だった。。。 問題へのリンク 問題概要 幅が マス、高さが のヒストグラムが与えられる。このヒストグラムの各マスを白黒に塗る方法のうち どの 2 × 2 の区間をとっても…
