DP遷移の集約・高速化
同じ形の遷移をprefix、単調構造、剰余類などでまとめる。
この典型を扱う単元: DP遷移を因数分解・集約して加速する
検索別名: DP optimization、DP高速化
未知問からこの典型を見つける手掛かり
- 扱う対象
- dp
- 状態数
- 遷移
- 遷移元
- 使う手掛かり
- 二重ループ
- 全遷移
- 遷移をまとめ
- 保つ不変量
- 区間和
- 単調
- 同じ係数
- 最小値
- 求めるもの
- 更新
- 計算量
- 高速化
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- Convex Hull Trick・直線包絡: DP遷移を直線の評価へ変形し、包絡線queryとして高速化する構成で併用する。
学習成果と学習単位
余分な歩行を訪問済みの最良状態での反復へ移す交換論を示し、有限prefix DPと閉形式のtailへ分離できる。
DP遷移を因数分解・集約して加速するで学ぶ遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。
DP遷移を因数分解・集約して加速するで学ぶ素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。
DP遷移を因数分解・集約して加速するで学ぶ全状態に共通する添字移動・倍率・affine作用を外出しし、旧値の保存と非可逆な作用を扱って例外だけを更新できる。
DP遷移を因数分解・集約して加速するで学ぶ隣接する出力の遷移式を比較し、共通項の消去と出入りする項から定数時間更新を導ける。
DP遷移を因数分解・集約して加速するで学ぶ全遷移の総和から禁止辺・禁止keyの集計値を引き、例外の総数で計算量を評価できる。
DP遷移を因数分解・集約して加速するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC212 E「Safety Journey」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC214 F「Substrings」 公式問題主題: 列・subsequence DP / 補助タグ
- ABC221 H「Count Multiset」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC224 E「Integers on Grid」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC224 F「Problem where +s Separate Digits」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC235 G「Gardens」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC243 G「Sqrt」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC249 E「RLE」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC253 E「Distance Sequence」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC263 E「Sugoroku 3」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC265 F「Manhattan Cafe」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC279 G「At Most 2 Colors」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC282 G「Similar Permutation」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC288 F「Integer Division」 公式問題主題: prefix分割DP / 補助タグ
- ABC311 F「Yet Another Grid Task」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC319 G「Counting Shortest Paths」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
技能・出典
主題: 状態グラフのモデリングと探索
主タグ: 状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析、DP遷移の集約・高速化、ordered set・multisetの動的順序管理
- ABC333 F「Bomb Game 2」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC334 F「Christmas Present 2」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC338 G「evall」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC342 F「Black Jack」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC353 G「Merchant Takahashi」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC358 G「AtCoder Tour」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC370 E「Avoid K Partition」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC372 F「Teleporting Takahashi 2」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC387 F「Count Arrays」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC408 F「Athletic」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC412 F「Socks 4」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC435 G「Domino Arrangement」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC436 G「Linear Inequation」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC442 F「Diagonal Separation 2」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ
- ABC446 G「221 Subsequence」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC457 F「Second Gap」 公式問題主題: DP遷移を因数分解・集約して加速する / 主タグ