区間の包含関係を除去できる
AtCoder
AtCoder600点
ARC-C
DP
区間
O(N^2)個のものを考える問題
区間分割型ナップサックDP
コーナーケース
場合分け
区間ソート
ワイルドカード問題
Yes/No判定問題
パズル
条件の言い換え
区間の包含関係を除去できる
とりうる状態が連結
黄色diff
コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…
Codeforces
EducationalCodeforces
in-place DP
DP
区間
区間ソート
DP高速化
DP高速化:累積和
累積和
前処理
各桁ごとに見る
各要素ごとに独立
区間の交差
区間の包含関係を除去できる
0と1の問題
数え上げ問題
いもす法
DP状態:その状態がどこまで続くのかを添字にもつ
DP高速化:オンラインオフライン変換
操作の流れを単純化する
CodeforcesR2500
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…