DP高速化:セグメント木上のin-placeDP
Codeforces
EducationalCodeforces
in-place DP
DP
区間
区間ソート
DP高速化
DP高速化:累積和
前処理
各桁ごとに見る
Greedy:各要素について独立に考えてよい
区間の交差
テク:区間の交差関係や包含関係を除去できる
0と1の問題
数え上げ問題
いもす法
DP状態:前回の最後の場所
操作の流れを単純化する
CodeforcesR2500
DP高速化:セグメント木
DP高速化:セグメント木上のin-placeDP
テク:2点や2区間の配置関係を考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
グラフ・盤面・数列の個数の数え上げ
N個の区間の問題
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…
AtCoder
AtCoder900点
ARC-F
in-place DP
DP
ナップサックDP
BIT
データ構造
DP高速化
DP高速化:セグメント木
区間
区間ソート
探索順序を工夫して解く
条件の言い換え
必要条件を列挙したら十分条件になる
制約条件:2-SAT
座標圧縮
数え上げ問題
コーナーケース
穴や盤外に落とす問題
一直線上のN点の問題
赤色diff
ロボット
操作:一斉に±aする
解空間:O(2^N)通りの選択肢
最適化テク:端点のみを考える
N個の点などを一律に動かす設定の問題
DP高速化:セグメント木上のin-placeDP
またしても、in-place DP のいい練習になった！！！ 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
AtCoder
AtCoder1000点
ARC-F
操作:上書き
区間
操作:区間
0と1の問題
DP
in-place DP
DP高速化:セグメント木
セグメント木
区間ソート
クエリ:区間
探索順序を工夫して解く
DP状態:前回の最後の場所
DP高速化
赤色diff
DP高速化:セグメント木上のin-placeDP
実家なんだと思うけど...意外とはまりやすい問題な気 がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…
