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数と状態・遷移数の積で見積もる。成分ラベルを正規化し、閉じた成分が後で再接続できないことを確認する。
問題一覧
- ABC248 F「Keep Connect」 公式問題
技能・出典
主題: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。)。 - ABC379 G「Count Grid 3-coloring」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: frontier/profile DP・境界状態圧縮 / 補助タグ: DPの最小十分状態
- ABC296 Ex「Unite」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: frontier/profile DP・境界状態圧縮 / 補助タグ: DPの最小十分状態
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC295 Ex「E or m」 公式問題
技能・出典
主題: subset zeta・Möbius変換(Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。)。主タグ: subset zeta・Möbius変換 / 補助タグ: frontier/profile DP・境界状態圧縮
- ABC309 G「Ban Permutation」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: frontier/profile DP・境界状態圧縮(未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。) / 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、frontier/profile DP・境界状態圧縮、部分集合・bitmask状態DP
前提・学習成果・出典
習得対象の目安: 黄色(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・境界状態圧縮の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。