グリッド・多次元表の局所DPを設計する
概要
グリッド・多次元表の局所DP
グリッド経路や多次元表の依存関係をDAG順に並べ、隣接する小さな状態集合から各セル・各添字を更新する。
考え方
二つの接頭辞(prefix)の長さや盤面の位置を状態にして、隣接する小状態から遷移する。表を埋める向きは依存関係から決め、値をどう集約するかは「その状態に何を保存するか」から決める。
経路数と最小費用で集約を使い分ける
右か下へ一マスずつ進む経路を数えるなら、各マスの値は「そこへ至る経路数」である。最後の一歩が上から来る経路と左から来る経路は重ならないので、二つの経路数を足す。障害物を0、穴のない開始点を1とし、盤外からの寄与は0にする。
一方、最小費用では、遷移元の値にその一手の費用を加え、候補のうち最小のものを選ぶ。例えば、文字列 の編集距離 を、 の長さ の接頭辞から の長さ の接頭辞への最小操作数とする。文字の添字は0始まりとし、削除・挿入・置換の費用は各1とする。空の接頭辞との距離は 、 で初期化する。 では、最後の操作を削除・挿入・一致または置換に分けると、
となる。角括弧は条件が真なら1、偽なら0を表す。三候補ですべての場合を尽くし、その最小値が最適な操作数になる。 を昇順に、同じ行の も昇順に計算すれば、上・左・左上の値はすべて既知になる。
最大正方形を三近傍から求める
穴のない正方形では、右下のマスを固定して考える。同じ右下を持つ正方形は小さいものから入れ子になり、大きいものが穴なしなら、それより小さいものもすべて穴なしである。そこで を「 を右下とする穴のない正方形の最大辺長」とする。行・列は1始まりで、穴のマスと盤外では0とする。
穴のないマスでは、上・左・左上の三つの値を使って、
と更新できる。このminは、最小費用のように候補から一つを選ぶ操作ではない。三方向すべての条件を満たす必要があるため、最も小さい辺長が拡張の限界になる。
辺長 の候補正方形を考える。その中には、上・左・左上のマスを右下とする辺長 の正方形が一つずつ含まれる。従って、候補が穴なしなら三つとも穴なしで、現在のマスにも穴がないことが必要である。逆に、この三つの小正方形を重ねると、候補のうち現在の右下マス以外をすべて覆う。現在のマスも穴なしなら候補全体が穴なしになるので、この条件は十分でもある。辺長1なら現在のマスだけを確認すればよく、三近傍の最小値が0でも式から1が得られる。
例えば、左上だけに穴がある次の3×3の盤面を考える。○は穴なし、×は穴を表す。
| 行・列 | 1 | 2 | 3 |
|---|---|---|---|
| 1 | × | ○ | ○ |
| 2 | ○ | ○ | ○ |
| 3 | ○ | ○ | ○ |
行を上から下へ、各行の列を左から右へ処理すると、最大辺長の表は次のようになる。
| 1列目 | 2列目 | 3列目 | |
|---|---|---|---|
| 1行目 | 0 | 1 | 1 |
| 2行目 | 1 | 1 | 2 |
| 3行目 | 1 | 2 | 2 |
1行目と1列目は、穴なら0、それ以外は盤外の0に制限されて1になる。 は上・左がともに1でも、左上が穴なので にとどまる。左上を参照せず上・左だけを見ると、穴を含む2×2を認めてしまう。 では三近傍がすべて1なので2となり、 も同様に2となる。最後の では上・左が2、左上が1なので、 となる。
最大辺長が なら、同じ右下を持つ辺長 の正方形が一つずつ存在し、 より大きいものは存在しない。従って、その右下で数える個数はちょうど 個である。各正方形の右下は一意なので、全マスの の総和で漏れも重複もなく数えられる。この例では1×1が8個、2×2が3個あり、表の総和も11になる。この対応を使うのが、下の問題一覧の先頭にあるABC311 Eである。
成立条件と計算量
縦 行、横 列の表で、各状態の遷移が定数個なら時間は 、全表を保存する空間も である。最大正方形のDPも一マスにつき三近傍を見るだけなので、この評価になる。
直前の行と現在の行だけを残すrolling配列なら、DPの作業空間は に減らせる。最大正方形を一行の配列で更新する場合は、上書き前の値が「上」、更新後の一つ前の値が「左」に当たり、古い「左上」を別変数に退避する。穴のマスでは古い値を残さず0にする。盤面自体を保存するならその空間は別に必要であり、編集距離の操作列や経路の復元にも追加情報が必要になる。
行優先順が使えるのは、各状態が上・左・左上など、先に処理する状態にだけ依存するためである。経路数でも、移動が右・下だけなら行・列は減らず、この依存順を保てる。上や左への移動も許すと循環が生じうるため、同じ順序で一度ずつ更新するだけでは一般に求められない。斜め遷移の向き、障害物、空の接頭辞などの境界状態も、問題ごとに確かめる。例えば最小費用で到達不能な状態は0ではなく無限大として扱う。最大辺長で使った「穴・盤外は0」を他のDPへそのまま流用しない。
問題一覧
- ABC311 E「Defect-free Squares」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。追加で学ぶ技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: DPの最小十分状態、グリッド・多次元表の局所DP
- ABC415 E「Hungry Takahashi」 公式問題
技能・出典
主題: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。主タグ: グリッド・多次元表の局所DP
- ABC443 E「Climbing Silver」 公式問題
技能・出典
主題: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。主タグ: グリッド・多次元表の局所DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC221 H「Count Multiset」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。 f[x][y]=f[x][y−x]+Σ_{直前M行k}f[k][y−x]。列ごとに行方向のsliding sumを保持してM項走査を消す。入る行を足し、出る行を引く順序を固定する。主タグ: DP遷移の集約・高速化 / 補助タグ: グリッド・多次元表の局所DP
- ABC227 F「Treasure Hunting」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: グリッド・多次元表の局所DP
- ABC259 Ex「Yet Another Path Counting」 公式問題主題: 平方根・閾値による軽重分類
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 平方根・閾値による軽重分類 / 補助タグ: 組合せ係数・数え上げ、グリッド・多次元表の局所DP
- ABC347 F「Non-overlapping Squares」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: グリッド・多次元表の局所DP、累積和・差分配列
- ABC358 G「AtCoder Tour」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(余分な歩行を訪問済みの最良状態での反復へ移す交換論を示し、有限prefix DPと閉形式のtailへ分離できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。 K歩DPを直接展開するとKに比例する。walkの余分な周回を訪問済み最大報酬の頂点での滞在へ移せるので、t≤HWだけDPし、dp[t][v]+(K−t)A_vを最大化する。巨大時間を短いprefixと線形tailへ分ける証明が核心。主タグ: DP遷移の集約・高速化 / 補助タグ: グリッド・多次元表の局所DP
- ABC464 E「Fill-Rect Query」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: グリッド・多次元表の局所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。