テク:区間の交差関係や包含関係を除去できる
AtCoder
AtCoder600点
ARC-C
DP
区間
解空間:O(N^2)通りの選択肢
区間分割型ナップサックDP
コーナーケース
場合分け
区間ソート
ワイルドカード問題
Yes/No判定問題
パズル
条件の言い換え
テク:区間の交差関係や包含関係を除去できる
連結性に着目する
黄色diff
N個の区間の問題
テク:2点や2区間の配置関係を考える
区間分割の仕方を走査する問題
区間の連結関係に関する問題
コーナーケースがえぐい！！ 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…
Codeforces
EducationalCodeforces
in-place DP
DP
区間
区間ソート
DP高速化
DP高速化:累積和
前処理
各桁ごとに見る
Greedy:各要素について独立に考えてよい
区間の交差
テク:区間の交差関係や包含関係を除去できる
0と1の問題
数え上げ問題
いもす法
DP状態:前回の最後の場所
操作の流れを単純化する
CodeforcesR2500
DP高速化:セグメント木
DP高速化:セグメント木上のin-placeDP
テク:2点や2区間の配置関係を考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
グラフ・盤面・数列の個数の数え上げ
N個の区間の問題
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…
AtCoder
AtCoder400点
ABC-D
区間
操作
XOR
0と1の問題
数列
しゃくとり法
累積和
二分探索
最適化テク:最適解の形を考える
最適化テク:解を変形していく(最適性を失わずに)
最適化テク:探索候補を絞る
操作の流れを単純化する
操作後の結果の最適化問題
操作:flip
最大スコア
緑色diff
区間の長さの最大値または最小値を求める
テク:区間の交差関係や包含関係を除去できる
テク:2点や2区間の配置関係を考える
disjointな区間の集合を管理する問題
操作をK回まで行える
ランレングス圧縮
テク:区間ごとに分割する
操作:区間
典型要素を詰め合わせた教育的問題
最適化問題
これ...以前 Twitter につぶやいた問題とよく似てた！！！ 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…
AtCoder
AtCoder700点
AGC-B
DP
テク:区間ごとに分割する
区間分割型ナップサックDP
変化・遷移が限られる
操作
条件の言い換え
操作:上書き
操作後の結果の数え上げ
数え上げ問題
ダブルカウントを防ぐ場合分け
操作:区間
水色diff
テク:区間の交差関係や包含関係を除去できる
区間分割の仕方を走査する問題
これは安定感のある思考過程を経て解けた気がするので共有したい気持ち！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。各 は 以上 以下の整数値である。今、以下のような操作を何回でも行うことができる: となるような < を選んで、 と との間の…
