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の評価費用も前計算へ含める。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠