グリッド・多次元表の局所DPを設計する

概要

グリッド・多次元表の局所DP

グリッド経路や多次元表の依存関係をDAG順に並べ、隣接する小さな状態集合から各セル・各添字を更新する。

考え方

二つの接頭辞(prefix)の長さや盤面の位置を状態にして、隣接する小状態から遷移する。表を埋める向きは依存関係から決め、値をどう集約するかは「その状態に何を保存するか」から決める。

経路数と最小費用で集約を使い分ける

右か下へ一マスずつ進む経路を数えるなら、各マスの値は「そこへ至る経路数」である。最後の一歩が上から来る経路と左から来る経路は重ならないので、二つの経路数を足す。障害物を0、穴のない開始点を1とし、盤外からの寄与は0にする。

一方、最小費用では、遷移元の値にその一手の費用を加え、候補のうち最小のものを選ぶ。例えば、文字列 A,BA,B の編集距離 D[i][j]D[i][j] を、AA の長さ ii の接頭辞から BB の長さ jj の接頭辞への最小操作数とする。文字の添字は0始まりとし、削除・挿入・置換の費用は各1とする。空の接頭辞との距離は D[i][0]=iD[i][0]=i、D[0][j]=jD[0][j]=j で初期化する。i,j≥1i,j\geq1 では、最後の操作を削除・挿入・一致または置換に分けると、

D[i][j]=min⁡{D[i−1][j]+1(削除)D[i][j−1]+1(挿入)D[i−1][j−1]+[A[i−1]≠B[j−1]](一致または置換)D[i][j]=\min\begin{cases} D[i-1][j]+1 & \text{(削除)}\\ D[i][j-1]+1 & \text{(挿入)}\\ D[i-1][j-1]+[A[i-1]\ne B[j-1]] & \text{(一致または置換)} \end{cases}

となる。角括弧は条件が真なら1、偽なら0を表す。三候補ですべての場合を尽くし、その最小値が最適な操作数になる。ii を昇順に、同じ行の jj も昇順に計算すれば、上・左・左上の値はすべて既知になる。

最大正方形を三近傍から求める

穴のない正方形では、右下のマスを固定して考える。同じ右下を持つ正方形は小さいものから入れ子になり、大きいものが穴なしなら、それより小さいものもすべて穴なしである。そこで dp[i][j]dp[i][j] を「(i,j)(i,j) を右下とする穴のない正方形の最大辺長」とする。行・列は1始まりで、穴のマスと盤外では0とする。

穴のないマスでは、上・左・左上の三つの値を使って、

dp[i][j]=1+min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])dp[i][j]=1+\min\bigl(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]\bigr)

と更新できる。このminは、最小費用のように候補から一つを選ぶ操作ではない。三方向すべての条件を満たす必要があるため、最も小さい辺長が拡張の限界になる。

辺長 n≥2n\geq2 の候補正方形を考える。その中には、上・左・左上のマスを右下とする辺長 n−1n-1 の正方形が一つずつ含まれる。従って、候補が穴なしなら三つとも穴なしで、現在のマスにも穴がないことが必要である。逆に、この三つの小正方形を重ねると、候補のうち現在の右下マス以外をすべて覆う。現在のマスも穴なしなら候補全体が穴なしになるので、この条件は十分でもある。辺長1なら現在のマスだけを確認すればよく、三近傍の最小値が0でも式から1が得られる。

例えば、左上だけに穴がある次の3×3の盤面を考える。○は穴なし、×は穴を表す。

行・列123
1×○○
2○○○
3○○○

行を上から下へ、各行の列を左から右へ処理すると、最大辺長の表は次のようになる。

dpdp1列目2列目3列目
1行目011
2行目112
3行目122

1行目と1列目は、穴なら0、それ以外は盤外の0に制限されて1になる。(2,2)(2,2) は上・左がともに1でも、左上が穴なので 1+min⁡(1,1,0)=11+\min(1,1,0)=1 にとどまる。左上を参照せず上・左だけを見ると、穴を含む2×2を認めてしまう。(2,3)(2,3) では三近傍がすべて1なので2となり、(3,2)(3,2) も同様に2となる。最後の (3,3)(3,3) では上・左が2、左上が1なので、1+min⁡(2,2,1)=21+\min(2,2,1)=2 となる。

最大辺長が kk なら、同じ右下を持つ辺長 1,2,…,k1,2,\ldots,k の正方形が一つずつ存在し、kk より大きいものは存在しない。従って、その右下で数える個数はちょうど kk 個である。各正方形の右下は一意なので、全マスの dpdp の総和で漏れも重複もなく数えられる。この例では1×1が8個、2×2が3個あり、表の総和も11になる。この対応を使うのが、下の問題一覧の先頭にあるABC311 Eである。

成立条件と計算量

縦 HH 行、横 WW 列の表で、各状態の遷移が定数個なら時間は O(HW)O(HW)、全表を保存する空間も O(HW)O(HW) である。最大正方形のDPも一マスにつき三近傍を見るだけなので、この評価になる。

直前の行と現在の行だけを残すrolling配列なら、DPの作業空間は O(W)O(W) に減らせる。最大正方形を一行の配列で更新する場合は、上書き前の値が「上」、更新後の一つ前の値が「左」に当たり、古い「左上」を別変数に退避する。穴のマスでは古い値を残さず0にする。盤面自体を保存するならその空間は別に必要であり、編集距離の操作列や経路の復元にも追加情報が必要になる。

行優先順が使えるのは、各状態が上・左・左上など、先に処理する状態にだけ依存するためである。経路数でも、移動が右・下だけなら行・列は減らず、この依存順を保てる。上や左への移動も許すと循環が生じうるため、同じ順序で一度ずつ更新するだけでは一般に求められない。斜め遷移の向き、障害物、空の接頭辞などの境界状態も、問題ごとに確かめる。例えば最小費用で到達不能な状態は0ではなく無限大として扱う。最大辺長で使った「穴・盤外は0」を他のDPへそのまま流用しない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。二次元以上の添字と依存順を定め、隣接状態から表を埋める。

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

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-grid-table

習得する技能

  • グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。

前提と範囲

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

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

このUnitを直接前提とする単元: frontier/profile DP・境界状態圧縮。

状態と遷移を定義できることを前提に、グリッドや多次元表の依存方向をDAGとして並べ、局所遷移で埋める。

このUnitでは扱わないもの

  • 一次元の初歩的なDP、部分集合・資源DP、および区間の分割点を列挙する区間DP。

根拠