テク:|x|=max(-x,x)
Codeforces
DP
区間分割型シーケンシャルDP
区間
DP状態:state
負値が本質的に効く問題
絶対値やminを扱う問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP高速化
DP高速化:直前との比較のみでよい
DP状態:長さの総和
数列
N個のペア値の問題
テク:|x|=max(-x,x)
DP状態:ビット
最大スコア
マルチテストケース問題
シーケンシャルDP
区間分割の仕方を走査する問題
最適化問題
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！ 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
AtCoder
AtCoder500点
ABC-E
緑色diff
マンハッタン距離
二次元平面上のN点の問題
解空間:O(N^2)通りの選択肢
絶対値やminを扱う問題
テク:45度回す
そのまま覚えたい典型問題
テク:2点や2区間の配置関係を考える
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
テク:|x|=max(-x,x)
解空間:O(N^2)個のペア
これ！！！！！HUPC 2019 day2 セットで出したやつや！！！ 問題へのリンク 問題概要 二次元平面上に 個の点 がある。 これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。 制約 考えたこと 2 点の位置関係としては、以下の 2 パターン…
全探索:bit全探索
Greedy
ある値を固定して考える
ABC-D
AtCoder
AtCoder400点
水色diff
全探索
Greedy:ある量を決めると残りが決まっていく
NoviSteps1Q
ある値を決めると解けるのでその値を探索する
絶対値やminを扱う問題
最適化問題
最大スコア
テク:|x|=max(-x,x)
場合分け
ABC 100 D - Patisserie ABC 問題概要 整数 3 つ組 (xi, yi, zi) が N 個与えられる。 このうちの M 個選んで、 (x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値) が最大になるようにせよ。 制約 1 <=…
