区間合成・領域分割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の上界をそのまま使わない。
問題一覧
- ABC217 F「Make Pair」 公式問題組合せ: 組合せ係数と対称性で数える
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 組合せ係数・数え上げ
- ABC252 G「Pre-Order」 公式問題
- ABC400 F「Happy Birthday! 3」 公式問題
- ABC292 G「Count Strictly Increasing Sequences」 公式問題
- ABC325 G「offence」 公式問題
- ABC233 G「Strongest Takahashi」 公式問題
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 累積和・差分配列
- ABC298 G「Strawberry War」 公式問題
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 有界全列挙・有限case分解、累積和・差分配列
- ABC261 G「Replace」 公式問題組合せ: 最短路モデル
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 最短路モデル
- ABC262 G「LIS with Stack」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC238 Ex「Removing People」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、区間合成・領域分割DP、法上の四則演算・高速累乗・逆元
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。