区間合成・領域分割DP

概要

区間・長方形の分割点を遷移にし、互いに独立な小領域の解を合成する。

区間[l,r)の解を、分割点mで得る独立な小区間の解から合成する。長さ昇順で処理し、空区間の単位元と、左右の選択を独立に掛けてよい条件を確かめる。消去・構文解析では、最初に対応させる端点を固定すると内側と外側へ分かれる。

ABC262 GはLISという題名でも、採用解法は位置区間と値区間を分割するDPである。末尾の支配関係だけでは状態を表せないため、この節で扱う。ABC233 G・298 Gは長方形への発展で、水平・垂直の切断と領域サイズ順の依存を比較する。

考え方

区間[l,r)を分割点mや対応する端点で分類し、より短い区間の解を合わせる。小区間の選択が独立となる条件と、同じ全体解が一意に分解されることを示す。

括弧化して最小費用を求める標準形ではdp[l][r]を区間[l,r)の値とし、一要素区間を基礎値で初期化する。長さ2,…,Nを昇順に、全l<m<rで dp[l][r]=min(dp[l][r],dp[l][m]+dp[m][r]+joinCost(l,m,r))。最後の合成の分割点mを固定すれば左右は短い同種の問題となる。計数の場合は左右個数を掛けて各mで足すが、同じ最終対象に複数の分解木を許すなら、そのままでは対象数ではなく分解木数を数える。

成立条件と計算量

O(N²)状態でO(N)分割ならO(N³)。長さ昇順で処理し、空区間の答えを固定する。長方形や値域を加えたDPでは状態数がさらに増えるため、一次元区間DPの上界をそのまま使わない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。小区間の独立性と長さ順の依存を確認し、分割点を遷移にする。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 列・編集距離・区間合成DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-interval-composition

区間合成・領域分割DP

習得する技能

  • 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: なし。

DPの最小十分状態で得た考え方と実装を再利用し、区間合成・領域分割DPの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 区間合成・領域分割DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠