prefix分割DP
概要
列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。
dp[r]をprefix [0,r)の答えとし、最後のブロック[l,r)を固定してdp[l]から遷移する。分割を一意に最後の切れ目へ対応させると、漏れ・重複のない漸化式になる。依存は短いprefixから長いprefixへ向かう。
ABC285 Eでは休日間の平日ブロックの価値を前計算する。ABC288 Fでは最後の数の桁を一つ延ばす式を用いて全切れ目の和をまとめる。区間合成と違い、最後のブロック自体を同種の区間DPで解くとは限らない。
ABC234 Gではdp[i]=Σ_{j<i}dp[j]·(max A[j,i)−min A[j,i))。最後の区間の寄与をmaxとminへ分け、各切れ目jの重みdp[j]を極値が等しい連続群ごとに単調stackへ持つ。右端追加で極値が更新される群をまとめて併合するため、各要素は高々一度push・popされる。
ABC374 Fでは、出荷を前へ詰めても待ち時間が悪化しないことから、出荷時刻をT_i+kXへ限定する。到着順に先頭から何個を出荷済みかと、候補時刻を状態にして、次の荷物のブロックを出荷するDPへ進む。候補を残してよい証明を先に行い、時刻差には圧縮順位でなく元の時刻を使う。
考え方
prefix [0,r)の最後のblock [l,r)を固定し、短いprefixの答えdp[l]へblockの評価を合成する。最後の切れ目による分類は分割を一意に表す。
最小費用ならdp[0]=0、他∞として、r=1,…,Nの順に合法な全l<rへ dp[r]=min(dp[r],dp[l]+cost(l,r))。数え上げならdp[0]=1として dp[r]+=dp[l]·ways(l,r)。waysはblock内部の選び方で、blockをただ切るだけなら合法時1である。各分割の最後の切れ目は一意なので、全分割を漏れなく重複なく扱う。最小値の更新時にlを保存し、r=Nからlへ戻れば実際のblock列も復元できる。空blockを許すと同じrへの依存が生じ、この前向きDPのままでは計算できない。
成立条件と計算量
N²個の切れ目をO(1)評価する素朴法はO(N²)。高速化では費用の分離、区間集約、単調stackなどの根拠を追加する。空prefixの単位元とblockの最短長を定め、blockの評価費用も前計算へ含める。
問題一覧
- ABC466 E「Range Flip」 公式問題組合せ: 交換論から選択順を導く
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: prefix分割DP / 補助タグ: 貪欲法と交換論
- ABC285 E「Work or Rest」 公式問題
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: prefix分割DP
- ABC288 F「Integer Division」 公式問題組合せ: DP遷移を因数分解・集約して加速する
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: DP遷移を因数分解・集約して加速する(遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。)。 最後の切れ目jを列挙するdp[i]=Σ_{j<i}dp[j] value(j+1..i)にvalue=10·旧value+d_iを代入する。dp[0]=1,dp[1]=d_1を初期値とし、i≥2ではdp[i]=10dp[i−1]+d_iΣ_{j<i}dp[j]となる。前答えと累積和だけでO(N)。主タグ: prefix分割DP / 補助タグ: DP遷移の集約・高速化
- ABC374 F「Shipping」 公式問題
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: prefix分割DP / 補助タグ: 座標・値の順序保存圧縮、DPの最小十分状態
- ABC230 F「Predilection」 公式問題
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: prefix分割DP
- ABC262 Ex「Max Limited Sequence」 公式問題
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: prefix分割DP / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、遅延評価する区間作用
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC228 H「Histogram」 公式問題
技能・出典
主題: Convex Hull Trick・直線包絡(一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Convex Hull Trick・直線包絡 / 補助タグ: prefix分割DP、貪欲法と交換論
- ABC234 G「Divide a Sequence」 公式問題
技能・出典
主題: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調stack・queueによる支配候補の削除 / 補助タグ: prefix分割DP
- ABC305 Ex「Shojin」 公式問題
技能・出典
主題: Lagrangian relaxation・Aliens trick(個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: prefix分割DP、貪欲法と交換論
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。最後の切れ目を固定し、漏れと重複のない分割の漸化式を立てる。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 列・編集距離・区間合成DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-prefix-partition
prefix分割DP
習得する技能
- 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: なし。
DPの最小十分状態で得た考え方と実装を再利用し、prefix分割DPの発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- prefix分割DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。