列・subsequence DP

概要

編集距離・sequence alignment DP

二つの列prefixを状態にし、一致・挿入・削除・置換の局所遷移から最小編集費用を求める。閾値がある場合は長さ差の下界で対角帯へ状態を絞る。

列のprefixや最後に選んだ要素を状態にし、順序を保つ選択を組み立てる。

左から処理し、未来の延長可能性が等しい履歴を同じ状態へまとめる。ABC327 Eでは、選択個数ごとにレートの式の分子を最大化する。末尾へ成績を追加したときの重みの変化を一つの更新式にまとめ、選ぶ・選ばないを比較する。

最後の位置、選択数、差分など、未来の可否や報酬に影響する情報を残す。LISの長さ別最小末尾への圧縮は、この一般の状態設計に支配関係を追加して導く。

考え方

処理済みprefixの答えを、次の一要素を選ぶ・選ばないという遷移で更新する。最後の値や選択数など、次の選択に必要な情報を状態へ加える。

選択個数を固定し、重み付きの分子を最大化する

ABC327 E「Maximize Rating」では、成績を元の順序を保って一つ以上選ぶ。選んだ個数を jj、選んだ成績を古い順に Q1,…,QjQ_1,\ldots,Q_j とすると、レートは次の式で決まる。

R=∑r=1j0.9j−rQr∑r=1j0.9j−r−1200jR=\frac{\sum_{r=1}^{j}0.9^{j-r}Q_r}{\sum_{r=1}^{j}0.9^{j-r}}-\frac{1200}{\sqrt{j}}

選ぶ個数が変わると、分母も罰則の項も変わる。まず jj を固定すると、この二つは選ぶ成績によらず、分母は正なので、分子が最大の選び方でレートも最大になる。そこでDPにはレートそのものではなく、選択個数ごとの分子の最大値を持つ。

全成績数を NN、元の列の ii 番目の成績を PiP_i とする。dp[i][j]dp[i][j] は「先頭 ii 個を処理し、その中から順序を保ってちょうど jj 個選んだときの分子の最大値」と定義する。ii は処理済みの個数、jj は選んだ個数であり、選ばない成績があれば両者は異なる。空の選択の分子は 00 とし、初期値を dp[0][0]=0dp[0][0]=0、それ以外を到達不能を表す −∞-\infty とする。

成績 PiP_i を選ばなければ、分子は dp[i−1][j]dp[i-1][j] のままである。選ぶ場合は、すでに選んだ j−1j-1 個の末尾へ追加する。例えば一つの成績 10001000 の後ろに 12001200 を加えると、分子は 10001000 から 0.9×1000+1200=21000.9\times1000+1200=2100 になる。古い成績はすべて「選んだ列の末尾からの距離」が一つ増え、重みが一律に 0.90.9 倍される。新しい成績の重みは 11 なので、分子全体の更新は「旧分子を 0.90.9 倍し、PiP_i を足す」でよい。

したがって、1≤j≤i≤N1\leq j\leq i\leq N について次の二候補を比較する。

dp[i][j]=max⁡(dp[i−1][j],  0.9 dp[i−1][j−1]+Pi)dp[i][j]=\max\bigl(dp[i-1][j],\;0.9\,dp[i-1][j-1]+P_i\bigr)

常に dp[i][0]=0dp[i][0]=0、j>ij>i は到達不能とする。到達不能な状態からは選ぶ遷移を行わない。任意の選び方は PiP_i を選ぶか選ばないかのどちらかに分かれるので、この二候補で漏れがない。また、同じ選択個数なら大きな分子ほど末尾追加後も大きい。倍率 0.90.9 が正なので大小関係が保たれ、各状態で最大値だけを残せる。

降順に更新して、同じ成績の再利用を防ぐ

前の行しか参照しないので、配列を一次元の dp[j]dp[j] へ圧縮できる。最初は dp[0]=0dp[0]=0、他を −∞-\infty とし、PiP_i を読むたびに j=i,i−1,…,1j=i,i-1,\ldots,1 の降順で次の更新を行う。

dp[j]←max⁡(dp[j],  0.9 dp[j−1]+Pi)dp[j]\leftarrow\max\bigl(dp[j],\;0.9\,dp[j-1]+P_i\bigr)

更新前の dp[j]dp[j] を候補に残すことが「今回は選ばない」に当たる。降順なら、参照する dp[j−1]dp[j-1] はまだ今回の成績で更新されておらず、必ず先頭 i−1i-1 個からの選択を表す。

二成績 P=(1000,1200)P=(1000,1200) で追うと、配列は次の順に変わる。dp[0]dp[0] は常に 00 のままとする。

処理・更新箇所dp[1]dp[1]dp[2]dp[2]
初期状態−∞-\infty−∞-\infty
P1=1000P_1=1000 で j=1j=110001000−∞-\infty
P2=1200P_2=1200 で j=2j=21000100021002100
同じ P2P_2 で j=1j=11200120021002100

二成績目では、まず旧 dp[1]=1000dp[1]=1000 から dp[2]=2100dp[2]=2100 を作る。その後、dp[1]dp[1] は「選ばない」候補の 10001000 と「選ぶ」候補の 12001200 を比較して 12001200 になる。もし昇順に更新すると、先に更新した dp[1]=1200dp[1]=1200 を読んで dp[2]=0.9×1200+1200=2280dp[2]=0.9\times1200+1200=2280 としてしまう。これは二成績目を二度選んだ不正な値である。二つの配列で旧行と新行を分ける場合は、この混同は起こらない。

全成績を処理したら、選択個数ごとの分母 WjW_j と罰則を戻す。分母は W0=0W_0=0、Wj=0.9Wj−1+1W_j=0.9W_{j-1}+1 で順に求められ、答えは次の最大値になる。

max⁡1≤j≤N(dp[j]Wj−1200j)\max_{1\leq j\leq N}\left(\frac{dp[j]}{W_j}-\frac{1200}{\sqrt{j}}\right)

小例では、一つ選ぶと 1200−1200=01200-1200=0、二つ選ぶと 2100/1.9−1200/2≃256.735022100/1.9-1200/\sqrt{2}\simeq256.73502 となり、後者を採用する。空の選択はDPの出発点にだけ使い、答えには含めない。最大レートが負になる入力もあるので、答えの初期値を 00 にしない。

ここで選択個数だけを添字にできたのは、処理済み位置を走査で管理し、次に選べる成績が過去の末尾に依存せず、分子の大小関係も末尾追加で保たれるためである。一般の部分列DPでは、直前の値や位置、公差などが次の選択を制限することもある。その場合は必要な情報を状態に残す。末尾の支配関係を使う圧縮はLIS・末尾の支配関係、許される末尾値の範囲から遷移を集約する方法は値域集約による部分列DPへ進む。

二つのprefixを扱う編集距離と帯DP

二列prefixの編集距離はグリッド・多次元表DPの三つの最後の操作と同じ漸化式で求められる。ここでの i,ji,j は二つの列の処理済みの長さであり、上の選択個数DPとは添字の意味が異なる。

二列の長さを N,MN,M、判定する距離の上限を KK とする。単位編集費用で距離 KK 以下だけを判定する場合、状態 (i,j)(i,j) への費用は長さ差 ∣i−j∣|i-j| 以上なので、∣i−j∣>K|i-j|>K を捨ててよい。各行で max⁡(0,i−K)≤j≤min⁡(M,i+K)\max(0,i-K)\leq j\leq\min(M,i+K) だけ計算し、帯外を ∞\infty、帯内の値を K+1K+1 で打ち切る。距離 KK 以下の実際の編集列は途中でも高々 KK の費用しか使わず帯外へ出られないため、この制限で有効解を落とさない。∣N−M∣>K|N-M|>K なら即不可能で、帯DPは O(N(K+1))O(N(K+1)) 時間、行の再利用で O(K+1)O(K+1) 空間となる。

空のprefix同士の距離は 00、片方だけが空なら距離はもう片方の長さになる。この基底も帯内だけ設定し、行を再利用するときは帯外の古い値を遷移元に使わない。

成立条件と計算量

段数 NN、各段 SS 状態・各状態から DD 遷移なら O(NSD)O(NSD)。同じ要素から連続して二回遷移しない更新順が必要。支配関係による圧縮には、残す状態がすべての未来に対して劣らないことの証明を付ける。

ABC327 Eでは ii 番目の成績につき ii 個の選択数を更新するため、合計 O(N2)O(N^2) 時間となる。一次元配列と分母の計算に必要な領域は O(N)O(N)。編集距離の帯DPでは、閾値 KK が各行の計算幅を制限する。選択数の軸を降順に更新することは領域の削減であり、この帯による状態数の削減とは区別する。

下位単元

問題一覧

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

関連問題

前提・学習成果・出典

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

根拠