ConvexHullTrick
Codeforces
操作
数列
辞書順
ConvexHullTrick
stack
非自明な線形時間
操作を好きな回数だけ行える
操作:区間
最適化テク:操作の流れを単純化する
区間分割型シーケンシャルDP
入れ子構造
Greedy
操作:上書き
平均値に関する問題
CodeforcesDIV1-C
CodeforcesR2100
操作後の結果の最適化問題
操作をstackを用いて高速化する
Greedy:辞書順最小を求める
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
Codeforces
数列
N個のペア値の問題
ConvexHullTrick
DP
分割統治法
DP高速化:MonotoneMinima
DP高速化
区間分割型シーケンシャルDP
誤差
オーバーフロー
Monge性
CodeforcesDIV1-C
CodeforcesR2400
高度典型
個人的要復習
sky さんの Monotone Minimma の例題！！！ 練習として解いてみた。 問題へのリンク 問題概要 (意訳) 個の値の組 , が与えられる。 で であり、 は狭義単調増加、 は狭義単調減少である。 を適切に定めたときのスコアが、 で与えられる。スコアの最小値を求…
Convex Hull Trick の練習に。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列を 個の区間に分割して、各区間 [, ] についての の総和を最小にせよ。 制約 解法 いかにも な DP になるのを頑張って高速化する系の問題。2 乗だから convex hull tri…
Convex Hull Trick の練習に。DP ではないけど、DP 高速化でよくやる Convex Hull Trick の構造そのものを試せる問題。Convex Hull Trick についての詳しい解説は Convex-Hull Trick (satanic さん) がとてもわかりやすい！ 問題へのリンク 問題概要 長さ の…
