meet-in-the-middle・半分全列挙

概要

二択が40回あると、全探索は約1兆通りになる。しかし20回ずつなら、各側は約100万通りで列挙できる。左右を別々に列挙し、一方の結果から必要な相手を検索することで、全組を作らずに答えを求めるのが半分全列挙(meet-in-the-middle)である。

使えるかを決めるのは、「半分なら列挙できる」ことと、「左右の結果を少ない情報で照合できる」ことの両方だ。この単元では、和を数える例から照合の仕組みを作り、経路や操作列へ広げる。

考え方

和そのものより、足りない和を探す

列 (1,2,3,2,4,5)(1,2,3,2,4,5) の添字をいくつか選び、対応する値の和を7にする方法を数えよう。同じ値でも添字が違えば別の要素とする。

6個すべての選ぶ・選ばないを決めると64通りある。まず前半 (1,2,3)(1,2,3) と後半 (2,4,5)(2,4,5) に分け、それぞれ8通りの部分和を作る。空の選択の和も0として含めると、整列した結果は次のようになる。

L=(0,1,2,3,3,4,5,6),R=(0,2,4,5,6,7,9,11).\begin{aligned} L&=(0,1,2,3,3,4,5,6),\\ R&=(0,2,4,5,6,7,9,11). \end{aligned}

左で和 xx を作ったなら、右で必要なのは 7−x7-x である。例えば左の和3には、値3だけを選ぶ方法と、値1と2を選ぶ方法の二つがある。右で値4を選ぶ方法と組み合わせれば、全体の選択は2通りできる。

左で和 xx を作る方法の数を fL(x)f_L(x)、右で和 yy を作る方法の数を fR(y)f_R(y) と書こう。次の表では、左の和ごとに必要な右の和 y=7−xy=7-x を並べ、最後の列に方法数の積 fL(x)fR(y)f_L(x)f_R(y) を示す。この積が、その行から全体の答えに加わる方法数である。

xxyyfL(x)f_L(x)fR(y)f_R(y)積
07111
16111
25111
34212
43100
52111
61100

答えは6通りとなる。ここで同じ和を集合にして消すと、左の和3を1通りと数えてしまう。同じ要約値でまとめられることと、元の選択を同一視してよいことは別である。

目標和を一般の TT とすると、左の和 xx に必要な右の和は T−xT-x になる。表の最後の列を足した計算は、次の式に一般化できる。

∑xfL(x)fR(T−x).\sum_x f_L(x)f_R(T-x).

左の選択を一つ、右の選択を一つ決めれば、その和集合が全体の選択になる。逆に全体の選択を左右へ制限すれば元の組に戻る。この一対一対応があるので、左右の方法数を掛け、左の和ごとに足せば漏れも重複もない。

片側の一覧を作り、もう片側から検索する

実装では次の手順にすればよい。

  1. 添字を左の kk 個と右の n−kn-k 個へ分ける。各側で使う添字が重ならないようにする。
  2. 右の部分和を、重複を残してすべて配列へ保存し、昇順に整列する。
  3. 左の選択を一つずつ列挙する。和が xx なら、右の配列で T−xT-x 以上となる最初の位置と、T−xT-x より大きくなる最初の位置を二分探索する。
  4. 二つの位置の差が、右の適合する選択数である。それを答えへ加える。

左を選択ごとに調べるので、左の同じ和が複数回現れても、そのたびに加算する。前の表のように頻度をまとめる実装なら、代わりに左右の頻度の積を足す。

各側の列挙は、現在の位置と和を持ち、次の要素を「選ばない」「選ぶ」の順に再帰すればよい。最初の和は0で、全要素を処理した時点の和を一つ出力する。選ぶ側では現在の和へその値を加えるだけなので、各候補を作るたびに最初から和を計算し直す必要はない。左の和は保存せず、生成した時点で検索に使える。

問いが変わると、残す情報も変わる

「和を TT にできるか」だけなら、同じ和には存在するという情報が一つあれば足りる。「一つの選び方を出力せよ」なら、各和について、選んだ添字を表すビットマスクなどを一つ残す。両側のマスクが見つかれば、それらを合わせて復元できる。全方法数を求める場合には、先ほどのように頻度が必要になる。

「和が TT 以下の最大値」に変わった場合、左の和 xx に対して右の和は T−xT-x 以下で最大のものを探す。右の整列配列で T−xT-x より大きい最初の位置を求め、その一つ前を候補にする。該当する要素がなければ、その左の選択からは解を作れない。

この検索は負数を含んでも使える。必要なのは部分和を整列できることだからだ。ただし、列挙途中の和が目標値を超えたという理由で枝を捨てる操作は、後で負数を選ぶと和が下がるため、一般には使えない。

経路は、出会う場所と累積値でつなぐ

ABC271 Fでは、正方形の盤面を右・下へ進む経路のうち、通ったマスの値のXOR(排他的論理和)が0になるものを数える。ここでは要素の集合でなく、移動列を分ける。

盤面を nn 行 nn 列、行・列番号を1始まりとする。1回進むたびに行番号と列番号の和は1増えるので、どの経路も i+j=n+1i+j=n+1 のマスをちょうど一つ通る。そこまでの移動は n−1n-1 回であり、後半も同じ長さになる。始点から右・下へ、終点から左・上へ、それぞれこの対角線まで列挙できる。

照合には、途中までのXORだけでなく、出会うマスの位置も必要だ。異なるマスで終わる二つの部分経路はつなげない。同じマス (i,j)(i,j) へ至る前半のXORを pp、後半のXORを qq、そのマスの値を ai,ja_{i,j} とし、両側とも出会うマスを含めて計算する。このとき全経路のXORは

p⊕q⊕ai,jp\oplus q\oplus a_{i,j}

となる。p⊕qp\oplus q だけでは、両側に含まれる出会いの値を2回使って打ち消してしまうため、もう一度加える。

例えば出会う値が5、前半が (1,2,5)(1,2,5)、後半が (5,6,6)(5,6,6) なら、p=6,q=5p=6,q=5 で、全体は 6⊕5⊕5=66\oplus5\oplus5=6 になる。マスの列 (1,2,5,6,6)(1,2,5,6,6) を直接計算しても6である。この例は条件を満たす経路ではなく、重なったマスの補正を確認するためのものだ。

XORが0になるための検索条件は q=p⊕ai,jq=p\oplus a_{i,j}。出会うマスごとに後半のXORを集め、前半の各経路からこの値の個数を検索する。全経路は出会うマスと前後の経路へ一意に分かれ、逆につなぐこともできるので、部分和の例と同じ方法数の積が使える。

成立条件と計算量

均等にするのは要素数より列挙の負担

二択が nn 回あり、左を kk 回、右を n−kn-k 回とすると、左右の列挙数は

SL=2k,SR=2n−kS_L=2^k,\qquad S_R=2^{n-k}

である。上の部分和の実装では、入力の読込み、左右の列挙、右の整列、左からの検索を合わせて

O(n+SL+SR+SRlog⁡(SR+1)+SLlog⁡(SR+1))O\bigl(n+S_L+S_R+S_R\log(S_R+1)+S_L\log(S_R+1)\bigr)

時間、入力・右の配列・再帰スタックを含め O(n+SR)O(n+S_R) 空間を使う。整数の和や比較を定数時間で扱えると仮定している。左右をほぼ同数に分ければ、時間は O(n2⌈n/2⌉)O(n2^{\lceil n/2\rceil})、空間は O(n+2⌈n/2⌉)O(n+2^{\lceil n/2\rceil}) に収まる。半分にしても指数時間なので、メモリに候補を保存できるかまで確認する。

要素ごとの選択肢数や一候補の処理費用が違う場合は、要素数だけを等しくしても均等にならない。ABC300 Gでは素因数を二群に割り当て、それぞれの群の素数だけから作れる積を列挙する。小さい素数は許される指数が大きいため、各群の素数の個数だけで負担を見積もれない。実際の列挙数と生成費用を評価する必要がある。

経路の場合も分岐回数を数える。ABC271 Fでは、各端から対角線までの部分経路数は、それぞれ合計 2n−12^{n-1}。ソートと二分探索で照合すれば O(n2n)O(n2^n) 時間になる。入力盤面と列挙結果を含む空間は O(n2+2n)O(n^2+2^n) である。経路全体を毎回コピーせず、位置と現在のXORを更新して列挙する評価だ。

境界と、適用を決める手がかり

空の選択も必ず列挙する。片側が0要素なら、その側の候補は和0の一つである。値0がある場合は、選ぶ場合と選ばない場合が同じ和になっても異なる選択なので、方法数を保つ。答えは最大で 2n2^n に達し、和も入力値より大きくなるので、どちらも整数型の範囲を確かめる。

半分全列挙は、全探索には大きすぎるが片側の候補を列挙できる規模で、相手の条件を和・XOR・大小・状態の一致などで検索できるときに候補になる。左右間の制約に履歴全体が必要なら、単に和だけを残す設計では足りない。境界情報を足しても一覧や照合が実行可能かを調べる。

非負整数の部分和で値の総和が小さいなら、到達できる和ごとに状態を持つDPのほうが少ない状態で済む場合もある。途中で同じ要約に達する履歴を頻繁にまとめられるなら、左右を最後まで列挙する前にDPで集約できないかも考えよう。

主配置問題で変わる「半分」の意味

ABC326 Fでは、奇数回の移動は縦、偶数回は横になる。各軸で必要な符号付き和の問題を作り、その選択をさらに半分にする。解を出力するには、和と一緒に符号の選び方を残す必要がある。

ABC336 Fでは、始点と目標の盤面からそれぞれ10手以内を探索して、同じ盤面で接続する。各操作が自身の逆操作なので、目標からの探索を後半の逆向き探索に使える。最短手数が欲しいため、同じ盤面へ達する方法数ではなく、各側の最短距離を残して距離の和を最小化する。20手より短い解も拾うため、ちょうど10手の状態だけに限定しない。

部分和・経路・盤面で残す情報は異なるが、「全体を左右へ分ける対応を作り、適合する相手を検索する」という設計は共通している。下の問題一覧では、各問題で照合に何を残すべきかを意識して読み進めよう。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。全列挙と整列・検索を組み合わせ、指数の半減と照合条件を設計する。

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

概念上の親: 探索空間を分けて照合・再帰分割する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-meet-in-the-middle

習得する技能

  • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

前提と範囲

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

直接の前提単元: なし。

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

探索対象を独立に列挙できる二集合へ分け、値・mask・境界を照合して指数を半減する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • meet-in-the-middle・半分全列挙の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠