部分集合・bitmask状態DP

概要

各bitの意味を固定し、訪問集合・選択集合・frontierなどの部分集合状態間を遷移する。

ABC309 Gは全N個の値の使用集合を持たず、走査位置の近傍2X−1個だけを残す発展例である。bitmaskという表記以上に、未来の禁止辺に接続しない値を忘れられることが状態削減の根拠になる。境界DPの節で、盤面のprofileと帯状matchingの共通原理を学ぶ。

ABC354 Eでは残存集合maskを状態とし、合法なpairを消すと要素数が2減る順序で勝敗を求める。集合状態とゲームの勝敗再帰を組み合わせる練習として扱う。

bitmaskで状態を書けることと、部分集合DPで解けることは別である。選択済み集合が増えるなどの非循環な順序を証明してから更新順を決める。ABC244 Fはbitを反転して閉路を持つ状態グラフになる比較例であり、状態グラフ探索の節を参照する。

考え方

訪問する順番を全て覚えると、候補は階乗個に増える。しかし、同じ集合を訪ねて同じ頂点にいるなら、その先で選べる行動と費用が同じになる場合がある。このときは「訪問済み集合と現在地」ごとに最良の値だけを残せる。少数の対象の集合を整数の各bitへ対応させた表現がbitmaskである。

訪問集合と最後の頂点を持つ

頂点を 0,1,…,N−10,1,\ldots,N-1 とし、頂点 ii を訪問済みならbit ii を1にする。bitは右から0,1,2,…と数え、1 << i はbit ii だけが1の整数を表す。以下の 001 などは2進表記であり、3頂点なら 001 は集合 {0}\{0\}、011 は {0,1}\{0,1\}、111 は {0,1,2}\{0,1,2\} を表す。

全頂点をちょうど一度ずつ訪ねる道をHamilton pathという。その最小費用を、始点 ss を固定して求めよう。dp[mask][v] を、始点 ss から mask に含まれる頂点をちょうど一度ずつ訪ね、頂点 vv で終わる道の最小費用とする。従って、有効な状態では始点 ss と終点 vv のbitがともに mask に含まれる。集合だけでは次の辺の費用が分からないため、最後の頂点も必要になる。

初期値は dp[1 << s][s] = 0、他は到達不能を表す ∞\infty とする。到達可能な dp[mask][v] から、未訪問の頂点 uu へ辺があるときだけ進む。辺 v→uv\to u の費用を w(v,u)w(v,u) とすると、更新は次の擬似コードになる。

next = mask | (1 << u)
dp[next][u] = min(dp[next][u], dp[mask][v] + w(v, u))

| はbitごとのORであり、未訪問だった頂点 uu のbitを1にする。始点0、辺 0→10\to1 の費用2、辺 1→21\to2 の費用3という小例では、次のように経路と状態が対応する。

経路mask最後の頂点この経路から得る更新候補
00010dp[001][0] に0
0→10111dp[011][1] に2
0→1→21112dp[111][2] に5

この表の配列添字も2進表記である。別の経路が同じ状態へ来たら、費用の小さい方を残す。例えば dp[011][2] は終点2が訪問集合に入っておらず、有効な状態ではない。

一回の遷移で訪問集合の要素数が一つ増えるので、集合サイズの昇順に処理すれば、更新元は先に確定している。逆に、初期状態以外の任意の合法な道から最後の頂点を外すと、必ず一つ小さい集合の状態と最後の辺に分けられる。従って、この遷移で全ての道を漏れなく比較できる。∞\infty の状態からは更新せず、実装では番兵値へ辺の費用を足さない。

どの集合で終了してよいかを決める

全頂点のbitが1のmaskを ALL = (1 << N) - 1 とする。Hamilton pathでは全訪問が必要なので、答えは ALL の終点別最小値、すなわち

min⁡0≤v<Ndp[ALL][v]\min_{0\leq v<N} dp[\mathrm{ALL}][v]

である。途中のmaskまで含めて最小化すると、訪問を終えていない道を答えにしてしまう。全候補が ∞\infty なら、そのような道は存在しない。N=1N=1 の道は始点だけからなり、初期値0がそのまま答えになる。

全訪問後に始点へ戻る閉路を求めるなら、終点 vv から始点 ss への辺がある候補について、dp[ALL][v]+w(v,s)dp[\mathrm{ALL}][v]+w(v,s) の最小値を取る。戻る辺のない候補は使えない。N=1N=1 で移動せず終了してよい問題なら、別途0とする。

一方、ABC274 E「Booster」では、街は全て訪ねるが、宝箱は訪ねなくてもよい。ここでは問題の記号に合わせて街を NN 個、宝箱を MM 個とし、街をbit 0,…,N−10,\ldots,N-1、宝箱をbit N,…,N+M−1N,\ldots,N+M-1 に対応させる。原点はmaskに入れず、出発・帰着地点として別に扱う。必須の街のmaskを need = (1 << N) - 1 とすると、終了候補は (mask & need) == need を満たす全てのmaskである。& はbitごとのANDであり、街のbitが全て立っているかを調べている。

例えば街2個・宝箱1個なら、終了できるmaskは 011 と 111。前者は宝箱を訪ねず、後者は宝箱も訪ねて帰る。取得した宝箱数を b(mask)b(\mathrm{mask}) とすると、現在の速度は 2b(mask)2^{b(\mathrm{mask})} と集合から復元できる。dp[mask][v] に最小所要時間を持ち、各点への原点からの距離で単点集合を初期化し、次の未訪問点までの距離を現在の速度で割って遷移する。宝箱へ着くまでの移動には、取得前の速度を使う。

最後は、必須bitを全て含むmaskと、その中の終点 vv について、原点へ戻る時間を加えた

dp[mask][v]+d(v,原点)2b(mask)dp[\mathrm{mask}][v]+\frac{d(v,\text{原点})}{2^{b(\mathrm{mask})}}

を比較する。ここで dd は2点間の距離である。全点を訪ねる ALL だけに限定すると、遠い宝箱を避ける解を取り逃がす。何を記録するかに加え、どの集合なら目的を達成したかを定めることが、任意の訪問対象を含むDPの要点である。この接続は公式問題文・個別公式解説に基づく(2026-10-26確認)。上の3頂点の小例は本単元用の独自例である。

集合の一部をまとめて選ぶ

一要素ずつ追加する代わりに、mask の部分集合 submask を一つのグループとして切り出すDPもある。mask の非空部分集合を全て調べるには、次の擬似コードを使う。

submask = mask
while submask != 0:
    submask を処理する
    submask = (submask - 1) & mask

mask = 101 なら、101 → 100 → 001 → 000 と進み、非空候補は集合 {0,2},{2},{0}\{0,2\},\{2\},\{0\} の3個となる。1を引くと最下位の1が0になり、それより下が1になる。& mask で元の集合にないbitを落とすと、元の集合のbitだけを使う次に小さい候補へ進める。この操作は部分集合を大きい順に一つずつたどるので、漏れも重複もない。

空集合も必要なら、ループの後で submask = 0 を一回だけ処理する。最初から mask = 0 の場合も、非空候補は0個、空集合込みなら1個である。0からさらに更新すると、通常のbit演算では (-1) & mask = mask に戻ってしまうため、0で停止する。

列挙の重複がなくても、分割の数え方には注意する。例えば集合 {0,2}\{0,2\} を二つの非空グループに分けるとき、submask = 001 と 100 は、切り出す側を交換しただけの同じ分割になる。グループに順序のない計数では、残りの集合の最小要素を含むグループから切り出すなど、一意な分解規則が必要である。最小値を取るDPでは同じ候補を二度比べても値は変わらないが、通り数を足すDPでは重複分だけ答えが増える。

成立条件と計算量

NN 個の対象から作る集合は 2N2^N 通りであり、集合だけを状態に持つならこの個数が出発点になる。ただし、状態数だけで実行時間は決まらず、各状態から何を列挙するかも数える。

  • 上のHamilton pathの標準形では、最後の頂点を加えて O(N2N)O(N2^N) 状態、各状態から次の頂点を最大 NN 個調べるため、時間 O(N22N)O(N^2 2^N)、領域 O(N2N)O(N2^N) となる。辺の費用を表に持つ場合の O(N2)O(N^2) の前処理・領域も、この全体評価に収まる。ABC274 Eでは対象数を N+MN+M に置き換える。
  • 全maskについてそのsubmaskを列挙すると、空も含む組の総数は 3N3^N になる。各要素は「maskの外」「submaskの中」「maskの中でsubmaskの外」の三択だからである。非空submaskだけなら、各maskの空集合を除いて 3N−2N3^N-2^N 組となる。一組を定数時間で評価するDPなら時間 O(3N)O(3^N) だが、各候補の費用計算やグループ数などの追加状態があれば、その分も含める。

適用には、同じ状態へまとめた履歴の未来が等しいことと、依存関係を非循環な順に処理できることの両方が必要になる。一要素追加なら集合サイズ昇順、要素を除いた集合に依存する再帰なら小さい集合から評価する。maskのbitを反転する遷移にはcycleがあり得るため、bitmaskという表記だけでDPを適用しない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。使用集合をbitmaskで持ち、集合の増減と遷移順から指数時間DPを設計する。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-subset-state

部分集合・bitmask状態DP

習得する技能

  • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

前提と範囲

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

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

このUnitを直接前提とする単元: frontier/profile DP・境界状態圧縮、Steiner tree subset DP、subset zeta・Möbius変換。

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

このUnitでは扱わないもの

  • 部分集合・bitmask状態DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠