ヒストグラム
AtCoder
黄色diff
ABC-G
スライド最小値
Cartesian木
ある量を固定して考える
制約:数値が10^6以下
ヒストグラム内の極大長方形の列挙
stack
左右からそれぞれ走査する
二次元グリッド
最大スコア
制約条件:長方形領域
縦方向と横方向の情報を整理する
前処理
絶対値やminを扱う問題
極大なものを考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
区間
最大値や最小値に着目する
ヒストグラム
AtCoder575点
操作をstackを用いて高速化する
最適化問題
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた! 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…
AtCoder
AtCoder300点
ABC-C
区間
操作:区間
操作
最小回数・最小個数を求める
ヒストグラム
0と1の問題
連結成分
主客転倒
ランレングス圧縮
茶色diff
for文
最適化問題
整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…
数え上げ問題
パリティ
DP
木DP
ヒストグラム
二次元グリッド
AtCoder
AtCoder1100点
AGC-D
再帰的構造に着目する
橙色diff
制約条件:正方形領域
制約条件:各グループの何かが等しい
解空間:O(2^N)通りの選択肢
市松模様・塗り分け
0と1の問題
なんか yukicoder で書いた問題に前半は似てた。でもこの問題の難しいところは後半の方だった。。。 問題へのリンク 問題概要 幅が マス、高さが のヒストグラムが与えられる。このヒストグラムの各マスを白黒に塗る方法のうち どの 2 × 2 の区間をとっても…