Monge性
AtCoder
有志コン
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP
ナップサックDP
DP状態:on/off
DP状態:state
DP高速化:直前との比較のみでよい
区間分割型ナップサックDP
DP高速化
f(i,j)をiとjとに分離する
数列
Monge性
DP高速化:Monge性の活用(LARSCH)
最適化テク:緩和しても良い
最大スコア
区間分割の仕方を走査する問題
区間
操作をstackを用いて高速化する
DP高速化:stackの活用
stack
最適化問題
これは学びの深い DP 問題! 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
yukicoder
全部混ぜて解く
探索順序を工夫して解く
Greedy
Greedy:どちらも可なら厳しい方
マッチング
Greedyなマッチング
二部マッチング
Greedy:交換しても悪化しない
二値パラメータ問題
setの上手な使い方
平面走査
Hallの結婚定理
Monge性
anti-Monge性
天才のGreedy
難しいGreedy
非自明な比較関数でソートする
めっちゃいい Greedy 問題だった!! 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…
Codeforces
DP
二次元グリッド
DP高速化
Monge性
制約条件:総和=K
単調性に着目する
数列
高速畳み込み計算
最適化テク:解を変形していく(最適性を失わずに)
戻すDP
分割統治法
N個のものうち1個を変更・削除したものを解く
ナップサックDP
部分和
CodeforcesDIV1-D
CodeforcesR2800
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
Codeforces
数列
二値パラメータ問題
ConvexHullTrick
DP
分割統治法
DP高速化:MonotoneMinima
DP高速化
区間分割型ナップサックDP
誤差
オーバーフロー
Monge性
CodeforcesDIV1-C
CodeforcesR2400
高度典型
個人的要復習
sky さんの Monotone Minimma の例題!!! 練習として解いてみた。 問題へのリンク 問題概要 (意訳) 個の値の組 , が与えられる。 で であり、 は狭義単調増加、 は狭義単調減少である。 を適切に定めたときのスコアが、 で与えられる。スコアの最小値を求…