meet-in-the-middle・半分全列挙
概要
二択が40回あると、全探索は約1兆通りになる。しかし20回ずつなら、各側は約100万通りで列挙できる。左右を別々に列挙し、一方の結果から必要な相手を検索することで、全組を作らずに答えを求めるのが半分全列挙(meet-in-the-middle)である。
使えるかを決めるのは、「半分なら列挙できる」ことと、「左右の結果を少ない情報で照合できる」ことの両方だ。この単元では、和を数える例から照合の仕組みを作り、経路や操作列へ広げる。
考え方
和そのものより、足りない和を探す
列 の添字をいくつか選び、対応する値の和を7にする方法を数えよう。同じ値でも添字が違えば別の要素とする。
6個すべての選ぶ・選ばないを決めると64通りある。まず前半 と後半 に分け、それぞれ8通りの部分和を作る。空の選択の和も0として含めると、整列した結果は次のようになる。
左で和 を作ったなら、右で必要なのは である。例えば左の和3には、値3だけを選ぶ方法と、値1と2を選ぶ方法の二つがある。右で値4を選ぶ方法と組み合わせれば、全体の選択は2通りできる。
左で和 を作る方法の数を 、右で和 を作る方法の数を と書こう。次の表では、左の和ごとに必要な右の和 を並べ、最後の列に方法数の積 を示す。この積が、その行から全体の答えに加わる方法数である。
| 積 | ||||
|---|---|---|---|---|
| 0 | 7 | 1 | 1 | 1 |
| 1 | 6 | 1 | 1 | 1 |
| 2 | 5 | 1 | 1 | 1 |
| 3 | 4 | 2 | 1 | 2 |
| 4 | 3 | 1 | 0 | 0 |
| 5 | 2 | 1 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
答えは6通りとなる。ここで同じ和を集合にして消すと、左の和3を1通りと数えてしまう。同じ要約値でまとめられることと、元の選択を同一視してよいことは別である。
目標和を一般の とすると、左の和 に必要な右の和は になる。表の最後の列を足した計算は、次の式に一般化できる。
左の選択を一つ、右の選択を一つ決めれば、その和集合が全体の選択になる。逆に全体の選択を左右へ制限すれば元の組に戻る。この一対一対応があるので、左右の方法数を掛け、左の和ごとに足せば漏れも重複もない。
片側の一覧を作り、もう片側から検索する
実装では次の手順にすればよい。
- 添字を左の 個と右の 個へ分ける。各側で使う添字が重ならないようにする。
- 右の部分和を、重複を残してすべて配列へ保存し、昇順に整列する。
- 左の選択を一つずつ列挙する。和が なら、右の配列で 以上となる最初の位置と、 より大きくなる最初の位置を二分探索する。
- 二つの位置の差が、右の適合する選択数である。それを答えへ加える。
左を選択ごとに調べるので、左の同じ和が複数回現れても、そのたびに加算する。前の表のように頻度をまとめる実装なら、代わりに左右の頻度の積を足す。
各側の列挙は、現在の位置と和を持ち、次の要素を「選ばない」「選ぶ」の順に再帰すればよい。最初の和は0で、全要素を処理した時点の和を一つ出力する。選ぶ側では現在の和へその値を加えるだけなので、各候補を作るたびに最初から和を計算し直す必要はない。左の和は保存せず、生成した時点で検索に使える。
問いが変わると、残す情報も変わる
「和を にできるか」だけなら、同じ和には存在するという情報が一つあれば足りる。「一つの選び方を出力せよ」なら、各和について、選んだ添字を表すビットマスクなどを一つ残す。両側のマスクが見つかれば、それらを合わせて復元できる。全方法数を求める場合には、先ほどのように頻度が必要になる。
「和が 以下の最大値」に変わった場合、左の和 に対して右の和は 以下で最大のものを探す。右の整列配列で より大きい最初の位置を求め、その一つ前を候補にする。該当する要素がなければ、その左の選択からは解を作れない。
この検索は負数を含んでも使える。必要なのは部分和を整列できることだからだ。ただし、列挙途中の和が目標値を超えたという理由で枝を捨てる操作は、後で負数を選ぶと和が下がるため、一般には使えない。
経路は、出会う場所と累積値でつなぐ
ABC271 Fでは、正方形の盤面を右・下へ進む経路のうち、通ったマスの値のXOR(排他的論理和)が0になるものを数える。ここでは要素の集合でなく、移動列を分ける。
盤面を 行 列、行・列番号を1始まりとする。1回進むたびに行番号と列番号の和は1増えるので、どの経路も のマスをちょうど一つ通る。そこまでの移動は 回であり、後半も同じ長さになる。始点から右・下へ、終点から左・上へ、それぞれこの対角線まで列挙できる。
照合には、途中までのXORだけでなく、出会うマスの位置も必要だ。異なるマスで終わる二つの部分経路はつなげない。同じマス へ至る前半のXORを 、後半のXORを 、そのマスの値を とし、両側とも出会うマスを含めて計算する。このとき全経路のXORは
となる。 だけでは、両側に含まれる出会いの値を2回使って打ち消してしまうため、もう一度加える。
例えば出会う値が5、前半が 、後半が なら、 で、全体は になる。マスの列 を直接計算しても6である。この例は条件を満たす経路ではなく、重なったマスの補正を確認するためのものだ。
XORが0になるための検索条件は 。出会うマスごとに後半のXORを集め、前半の各経路からこの値の個数を検索する。全経路は出会うマスと前後の経路へ一意に分かれ、逆につなぐこともできるので、部分和の例と同じ方法数の積が使える。
成立条件と計算量
均等にするのは要素数より列挙の負担
二択が 回あり、左を 回、右を 回とすると、左右の列挙数は
である。上の部分和の実装では、入力の読込み、左右の列挙、右の整列、左からの検索を合わせて
時間、入力・右の配列・再帰スタックを含め 空間を使う。整数の和や比較を定数時間で扱えると仮定している。左右をほぼ同数に分ければ、時間は 、空間は に収まる。半分にしても指数時間なので、メモリに候補を保存できるかまで確認する。
要素ごとの選択肢数や一候補の処理費用が違う場合は、要素数だけを等しくしても均等にならない。ABC300 Gでは素因数を二群に割り当て、それぞれの群の素数だけから作れる積を列挙する。小さい素数は許される指数が大きいため、各群の素数の個数だけで負担を見積もれない。実際の列挙数と生成費用を評価する必要がある。
経路の場合も分岐回数を数える。ABC271 Fでは、各端から対角線までの部分経路数は、それぞれ合計 。ソートと二分探索で照合すれば 時間になる。入力盤面と列挙結果を含む空間は である。経路全体を毎回コピーせず、位置と現在のXORを更新して列挙する評価だ。
境界と、適用を決める手がかり
空の選択も必ず列挙する。片側が0要素なら、その側の候補は和0の一つである。値0がある場合は、選ぶ場合と選ばない場合が同じ和になっても異なる選択なので、方法数を保つ。答えは最大で に達し、和も入力値より大きくなるので、どちらも整数型の範囲を確かめる。
半分全列挙は、全探索には大きすぎるが片側の候補を列挙できる規模で、相手の条件を和・XOR・大小・状態の一致などで検索できるときに候補になる。左右間の制約に履歴全体が必要なら、単に和だけを残す設計では足りない。境界情報を足しても一覧や照合が実行可能かを調べる。
非負整数の部分和で値の総和が小さいなら、到達できる和ごとに状態を持つDPのほうが少ない状態で済む場合もある。途中で同じ要約に達する履歴を頻繁にまとめられるなら、左右を最後まで列挙する前にDPで集約できないかも考えよう。
主配置問題で変わる「半分」の意味
ABC326 Fでは、奇数回の移動は縦、偶数回は横になる。各軸で必要な符号付き和の問題を作り、その選択をさらに半分にする。解を出力するには、和と一緒に符号の選び方を残す必要がある。
ABC336 Fでは、始点と目標の盤面からそれぞれ10手以内を探索して、同じ盤面で接続する。各操作が自身の逆操作なので、目標からの探索を後半の逆向き探索に使える。最短手数が欲しいため、同じ盤面へ達する方法数ではなく、各側の最短距離を残して距離の和を最小化する。20手より短い解も拾うため、ちょうど10手の状態だけに限定しない。
部分和・経路・盤面で残す情報は異なるが、「全体を左右へ分ける対応を作り、適合する相手を検索する」という設計は共通している。下の問題一覧では、各問題で照合に何を残すべきかを意識して読み進めよう。
問題一覧
- ABC271 F「XOR on Grid Path」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。 - ABC427 F「Not Adjacent」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。 - ABC402 F「Path to Integer」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。 - ABC326 F「Robot Rotation」 公式問題組合せ: 成立証明から構成解を復元する
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 構成解・witness復元
- ABC336 F「Rotation Puzzle」 公式問題組合せ: 状態グラフのモデリングと探索
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 状態グラフのモデリングと探索
- ABC464 F「Random Vault Heist」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元
- ABC300 G「P-smooth number」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 尺取り法・sliding window
- ABC252 Ex「K-th beautiful Necklace」 公式問題組合せ: bit列をTrieで索引化する
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: binary Trieによるbit列索引
- ABC220 H「Security Camera」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 分離可能線形変換・Walsh–Hadamard変換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 水色(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・半分全列挙の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。
根拠
- ABC300 G 公式問題文・個別公式解説 — 素因数を二群へ分けた積の列挙と、列挙数による負担の調整。
- ABC336 F 公式問題文・個別公式解説 — 始点と目標からの探索、状態と最短距離の照合。
- ABC326 F 公式問題文・個別公式解説 — 軸ごとの分解、符号付き和の照合と復元。
- ABC220 H 公式解説
- ABC220 H 公式問題文
- ABC252 H 公式解説
- ABC252 H 公式問題文
- ABC271 F 公式解説
- ABC271 F 公式問題文