frontier/profile DP・境界状態圧縮

概要

走査済み領域と未走査領域の境界だけに未来へ影響する色・値の使用済みフラグ・接続partitionを保持し、必要なら同値な接続ラベルを正規化して幅指数で遷移する。

まずABC248 Fの幅2の接続状態を学び、ABC379 Gで最後の一行の色だけを保持する。次にABC309 Gでは位置iの近傍にある値の使用済みフラグを残す。窓から外れた値は未来の禁止辺に接続しないため、その使用状況を忘れても後続の選択肢は変わらない。

ABC309 Gは包除で固定する位置数kと、幅2X−1の窓のmaskを持つ部分matching計数である。未固定部分の(N−k)!と符号(−1)^kを最後に掛ける。指数部分を全体サイズNから帯幅Xへ移すことが核心である。

ABC296 Exでは色や使用済みbitだけでは足りず、境界上の黒マス同士が既に接続しているかをpartitionとして保持する。同じ接続関係のラベルを正規化し、成分が境界から消えると後から接続できないことも遷移条件に含める。

考え方

走査境界を越えて未来と接続する情報だけを持ち、過去の内部を忘れる。盤面の占有状態、括弧や連結成分ラベル、帯状matchingの近傍集合がprofileになる。

幅wの盤面を行優先で走査するdomino敷き詰めでは、次のwマスの予約済み状態をmaskに持つ。dp[0]=1から、現在bit0が予約済みならmask>>1へ進む。未予約なら右マスが同じ行内かつbit1未予約のとき横dominoを置いて (mask OR 2)>>1、下マスが存在するとき縦dominoを置いて (mask>>1) OR (1<<(w−1)) へ遷移する。障害物では予約bitが立っていれば不正、立っていなければshiftだけ行う。全マス終了時にmask=0の値を返す。

未処理領域へ影響するのは予約済みのマスだけで、過去の敷き方は追加の制約を持たないため、このmaskへまとめて個数を加算できる。連結性問題なら占有bitだけでは不足し、境界頂点が過去でつながる同値類をpartitionとして追加する。labelは出現順に0,1,…へ正規化し、同じpartitionの異なる番号付けを別状態にしない。

成立条件と計算量

境界幅wに対する状態数は一般に指数で、連結分割を持つと単純な2^wを超える。cell数と状態・遷移数の積で見積もる。成分ラベルを正規化し、閉じた成分が後で再接続できないことを確認する。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。境界から離れた情報を忘れ、接続関係を正規化した幅指数の状態を設計する。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-frontier-profile-dp

frontier/profile DP・境界状態圧縮

習得する技能

  • 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。

前提と範囲

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

直接の前提単元: グリッド・多次元表の局所DPを設計する、最小十分状態からDPを設計する、部分集合・bitmask状態DP。

このUnitを直接前提とする単元: なし。

DPの最小十分状態で得た考え方と実装を再利用し、frontier/profile DP・境界状態圧縮の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • frontier/profile DP・境界状態圧縮の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠