区間拡張DP
概要
訪問済み範囲と現在いる端を状態にし、未訪問の左右の隣点へ拡張する。
数直線上で隣の未訪問点へ進むとき、訪問済みの点は連続区間になる。dp[l][r][side]で訪問済み範囲と現在いる端を表し、l−1またはr+1へ進む。区間長が増えるので、移動方向が左右へ反転してもDPの依存は循環しない。
ABC273 Fでは壁を越えるのに必要な鍵が訪問済み区間にあるかを判定する。続くABC219 Hでは将来回収する本数kを追加し、移動距離dによる損失k·dを評価する。区間の左右を独立に解いて合成するDPとは、状態の意味も遷移方向も異なる。
考え方
数直線上の点を隣から訪問すると、訪問済み集合は連続区間になる。左右端と現在地がどちらの端かを状態にし、外側の隣点への移動を遷移として持つ。
座標x_0≤…≤x_{N−1}上で開始位置sを含む訪問区間[l,r]を持ち、dp[l][r][0/1]を現在地が左端/右端である最小費用とする。dp[s][s][両端]=0、他∞。現在位置p=x_lまたはx_rから、l>0ならdp[l−1][r][0]へ|p−x_{l−1}|を、r+1<Nならdp[l][r+1][1]へ|p−x_{r+1}|を足してmin更新する。区間長の昇順で処理すれば依存は非循環。移動費用が残る対象数に比例するなら、その時点の未訪問数を距離へ掛ける。遠い点へ移動する際に途中の点を訪問済みへ含めても不利益がないことが、連続区間への正規化の前提となる。
成立条件と計算量
定数の追加状態ならO(N²)状態・遷移。残り個数や時間を持つ場合はその数を掛ける。壁や鍵の条件は訪問済み区間から判定する。座標圧縮後も移動距離は元座標の差を使う。
問題一覧
- ABC273 F「Hammer 2」 公式問題
技能・出典
主題: 区間拡張DP(訪問済み範囲と現在いる端を状態にし、未訪問の左右の隣点へ拡張する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。)。主タグ: 区間拡張DP / 補助タグ: 座標・値の順序保存圧縮
- ABC219 H「Candles」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 区間拡張DP(訪問済み範囲と現在いる端を状態にし、未訪問の左右の隣点へ拡張する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 区間拡張DP / 補助タグ: 寄与の数え上げと順序交換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。訪問済み範囲と現在の端で履歴を圧縮し、移動が往復しても非循環なDPを作る。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 列・編集距離・区間合成DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-interval-expansion
区間拡張DP
習得する技能
- 訪問済み範囲と現在いる端を状態にし、未訪問の左右の隣点へ拡張する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: なし。
DPの最小十分状態で得た考え方と実装を再利用し、区間拡張DPの発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 区間拡張DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。