列・subsequence DP
概要
編集距離・sequence alignment DP
二つの列prefixを状態にし、一致・挿入・削除・置換の局所遷移から最小編集費用を求める。閾値がある場合は長さ差の下界で対角帯へ状態を絞る。
列のprefixや最後に選んだ要素を状態にし、順序を保つ選択を組み立てる。
左から処理し、未来の延長可能性が等しい履歴を同じ状態へまとめる。ABC327 Eでは、選択個数ごとにレートの式の分子を最大化する。末尾へ成績を追加したときの重みの変化を一つの更新式にまとめ、選ぶ・選ばないを比較する。
最後の位置、選択数、差分など、未来の可否や報酬に影響する情報を残す。LISの長さ別最小末尾への圧縮は、この一般の状態設計に支配関係を追加して導く。
考え方
処理済みprefixの答えを、次の一要素を選ぶ・選ばないという遷移で更新する。最後の値や選択数など、次の選択に必要な情報を状態へ加える。
選択個数を固定し、重み付きの分子を最大化する
ABC327 E「Maximize Rating」では、成績を元の順序を保って一つ以上選ぶ。選んだ個数を 、選んだ成績を古い順に とすると、レートは次の式で決まる。
選ぶ個数が変わると、分母も罰則の項も変わる。まず を固定すると、この二つは選ぶ成績によらず、分母は正なので、分子が最大の選び方でレートも最大になる。そこでDPにはレートそのものではなく、選択個数ごとの分子の最大値を持つ。
全成績数を 、元の列の 番目の成績を とする。 は「先頭 個を処理し、その中から順序を保ってちょうど 個選んだときの分子の最大値」と定義する。 は処理済みの個数、 は選んだ個数であり、選ばない成績があれば両者は異なる。空の選択の分子は とし、初期値を 、それ以外を到達不能を表す とする。
成績 を選ばなければ、分子は のままである。選ぶ場合は、すでに選んだ 個の末尾へ追加する。例えば一つの成績 の後ろに を加えると、分子は から になる。古い成績はすべて「選んだ列の末尾からの距離」が一つ増え、重みが一律に 倍される。新しい成績の重みは なので、分子全体の更新は「旧分子を 倍し、 を足す」でよい。
したがって、 について次の二候補を比較する。
常に 、 は到達不能とする。到達不能な状態からは選ぶ遷移を行わない。任意の選び方は を選ぶか選ばないかのどちらかに分かれるので、この二候補で漏れがない。また、同じ選択個数なら大きな分子ほど末尾追加後も大きい。倍率 が正なので大小関係が保たれ、各状態で最大値だけを残せる。
降順に更新して、同じ成績の再利用を防ぐ
前の行しか参照しないので、配列を一次元の へ圧縮できる。最初は 、他を とし、 を読むたびに の降順で次の更新を行う。
更新前の を候補に残すことが「今回は選ばない」に当たる。降順なら、参照する はまだ今回の成績で更新されておらず、必ず先頭 個からの選択を表す。
二成績 で追うと、配列は次の順に変わる。 は常に のままとする。
| 処理・更新箇所 | ||
|---|---|---|
| 初期状態 | ||
| で | ||
| で | ||
| 同じ で |
二成績目では、まず旧 から を作る。その後、 は「選ばない」候補の と「選ぶ」候補の を比較して になる。もし昇順に更新すると、先に更新した を読んで としてしまう。これは二成績目を二度選んだ不正な値である。二つの配列で旧行と新行を分ける場合は、この混同は起こらない。
全成績を処理したら、選択個数ごとの分母 と罰則を戻す。分母は 、 で順に求められ、答えは次の最大値になる。
小例では、一つ選ぶと 、二つ選ぶと となり、後者を採用する。空の選択はDPの出発点にだけ使い、答えには含めない。最大レートが負になる入力もあるので、答えの初期値を にしない。
ここで選択個数だけを添字にできたのは、処理済み位置を走査で管理し、次に選べる成績が過去の末尾に依存せず、分子の大小関係も末尾追加で保たれるためである。一般の部分列DPでは、直前の値や位置、公差などが次の選択を制限することもある。その場合は必要な情報を状態に残す。末尾の支配関係を使う圧縮はLIS・末尾の支配関係、許される末尾値の範囲から遷移を集約する方法は値域集約による部分列DPへ進む。
二つのprefixを扱う編集距離と帯DP
二列prefixの編集距離はグリッド・多次元表DPの三つの最後の操作と同じ漸化式で求められる。ここでの は二つの列の処理済みの長さであり、上の選択個数DPとは添字の意味が異なる。
二列の長さを 、判定する距離の上限を とする。単位編集費用で距離 以下だけを判定する場合、状態 への費用は長さ差 以上なので、 を捨ててよい。各行で だけ計算し、帯外を 、帯内の値を で打ち切る。距離 以下の実際の編集列は途中でも高々 の費用しか使わず帯外へ出られないため、この制限で有効解を落とさない。 なら即不可能で、帯DPは 時間、行の再利用で 空間となる。
空のprefix同士の距離は 、片方だけが空なら距離はもう片方の長さになる。この基底も帯内だけ設定し、行を再利用するときは帯外の古い値を遷移元に使わない。
成立条件と計算量
段数 、各段 状態・各状態から 遷移なら 。同じ要素から連続して二回遷移しない更新順が必要。支配関係による圧縮には、残す状態がすべての未来に対して劣らないことの証明を付ける。
ABC327 Eでは 番目の成績につき 個の選択数を更新するため、合計 時間となる。一次元配列と分母の計算に必要な領域は 。編集距離の帯DPでは、閾値 が各行の計算幅を制限する。選択数の軸を降順に更新することは領域の削減であり、この帯による状態数の削減とは区別する。
下位単元
- LIS・末尾の支配関係 — 水色
- 値域集約による部分列DP — 水色
問題一覧
- ABC327 E「Maximize Rating」 公式問題
- ABC362 E「Count Arithmetic Subsequences」 公式問題
- ABC315 F「Shortcuts」 公式問題組合せ: 幾何の基本判定と座標変換
技能・出典
主題: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 列・subsequence DP / 補助タグ: 幾何の基本判定・配置・座標変換
- ABC386 F「Operate K」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: 列・subsequence DP(二つの列prefixを状態にし、一致・挿入・削除・置換の編集費用を最小化できる。閾値Kの判定では長さ差の下界から|i-j|≤Kの対角帯だけを計算できる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: 編集距離・sequence alignment DP / 補助タグ: DPの最小十分状態
- ABC214 F「Substrings」 公式問題組合せ: DP遷移を因数分解・集約して加速する
技能・出典
主題: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。既習技能: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。 同じ文字の直前出現と隣接禁止から、末尾追加が重複しない直前状態の区間[L_i,R_i]を導く。その後dp[i]=Σ_{j=L_i}^{R_i}dp[j]をprefix差へ変形する。境界の正当化が計数の核心。主タグ: 列・subsequence DP / 補助タグ: DP遷移の集約・高速化
- ABC238 F「Two Exams」 公式問題
- ABC299 F「Square Subsequence」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC225 F「String Cards」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: 列・subsequence DP
- ABC237 F「|LIS| = 3」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: LIS・末尾の支配関係(同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: DPの最小十分状態 / 補助タグ: LIS・末尾の支配関係
- ABC242 Ex「Random Painting」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 確率・期待値DP / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、列・subsequence DP
- ABC246 Ex「01? Queries」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。主タグ: 区間monoid要約 / 補助タグ: 列・subsequence DP
- ABC345 E「Colorful Subsequence」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 列・subsequence DP(列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。)。主タグ: DPの最小十分状態 / 補助タグ: 列・subsequence DP
- ABC457 G「Catch All Apples」 公式問題
技能・出典
主題: 半順序・Dilworth・最大反鎖(対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。)。既習技能: LIS・末尾の支配関係(同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 半順序・Dilworth・最大反鎖 / 補助タグ: 幾何の基本判定・配置・座標変換、LIS・末尾の支配関係
前提・学習成果・出典
習得対象の目安: 緑色(800–1199)。選ぶ・選ばない遷移と最後の要素を状態にし、同じ要素の重複利用を避ける。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 列・編集距離・区間合成DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-sequence
列・subsequence DP
習得する技能
- 二つの列prefixを状態にし、一致・挿入・削除・置換の編集費用を最小化できる。閾値Kの判定では長さ差の下界から|i-j|≤Kの対角帯だけを計算できる。
- 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: LIS・末尾の支配関係、値域集約による部分列DP、半順序・Dilworth・最大反鎖。
DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 列・subsequence DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。