探索空間を分けて照合・再帰分割する

概要

全体を一度に調べるのが難しいときは、小さい部分について何を求めれば、全体の答えを復元できるかを考える。部分ごとの計算が軽く、復元も軽ければ、扱える入力を大きくできる。

この単元では、二つの分け方を区別する。一つは、選択を左右へ分けて列挙し、条件を満たす組を検索する方法。もう一つは、同じ形の小問題を再帰的に解き、左右の答えと境界をまたぐ処理から親の答えを作る方法である。分割点を決めるだけでなく、分割後に残す情報と合成の費用まで設計する。

考え方

選択を分け、相手に必要な条件を求める

四つの値 (2,5,1,6)(2,5,1,6) からいくつか選び、和を8にする方法を数えよう。素朴には、それぞれを選ぶかどうかの 24=162^4=16 通りを調べる。

ここで、前の二つと後ろの二つを別々に扱ってみる。左の部分和は (0,2,5,7)(0,2,5,7)、右の部分和は (0,1,6,7)(0,1,6,7) である。左で2を作ったなら、右では6を探せばよい。左で7を作ったなら、右では1を探す。該当する選び方は、値2と6を選ぶもの、値2と5と1を選ぶものの2通りになる。

なぜこれで全部を数えたことになるのか。元の選択は「左で選んだ添字の集合」と「右で選んだ添字の集合」にただ一通りに分かれる。逆に左右の選択を一つずつ取れば、元の選択がただ一つ決まる。この対応を作ったうえで、左右の全組を試さず、必要な相手を検索するのが半分全列挙の核心である。

各要素を選ぶかどうかの nn 個の決定を、左の kk 個と右の n−kn-k 個へ分けると、列挙数は 2k2^k と 2n−k2^{n-k} になる。ただし、列挙後に全組を比較すれば 2k2n−k=2n2^k2^{n-k}=2^n に戻ってしまう。和が目標値 TT になる条件なら、左の和 xx に必要な右の和を T−xT-x と書き、整列した配列などで探す。この「照合条件を簡単に書けるか」が最初の判断になる。

小問題の答えに、合成に必要な情報を添える

次は列 (4,1,3,2)(4,1,3,2) にある転倒を数えよう。転倒とは、左にある要素の値が右にある要素の値より大きい添字の組である。

中央で分けると、転倒には「左半分の内部」「右半分の内部」「左から右をまたぐもの」の三種類がある。左の (4,1)(4,1) には1個、右の (3,2)(3,2) にも1個ある。しかし、この二つの個数だけでは、左右をまたぐ転倒が何個あるか分からない。

そこで、子の答えとして個数に加えて整列済みの列を返す。左右は (1,4)(1,4) と (2,3)(2,3) になる。これを小さい順に併合するとき、右の2を取り出す段階では左に4が残っているので、転倒が1個見つかる。右の3についても1個見つかり、合計は 1+1+2=41+1+2=4 個になる。

整列も同じ方法で左右へ分けられ、長さ1ならすでに整列済みで転倒は0個である。小問題を解いて必要な情報を返し、親で合成する流れを長さ1まで繰り返せる。これが分割統治である。重要なのは再帰を書くことよりも、「子が何を返せば、親の未処理分を安く求められるか」を決めることだ。

成立条件と計算量

何を小さくし、どこに費用が残るか

二つの手法を、次の四つの観点で比べよう。

  • 何を分けるか。 半分全列挙では、選択・経路・操作列などの探索空間を分ける。分割統治では、入力区間・値の集合・時刻区間などから、同じ形の小問題を作る。
  • 何を残すか。 半分全列挙では、相手を探すための値や境界情報を残し、要求に応じて個数や復元情報を添える。分割統治では、小問題の答えに、親の処理に必要な整列列や表を添える。転倒数では、個数だけでなく整列済みの列が必要だった。
  • どう合成を軽くするか。 半分全列挙では、左右の全組比較を検索や走査に置き換える。分割統治では、子で解いた部分を再計算せず、親で残った仕事を処理する。転倒数なら、左右内部の答えを受け取り、境界をまたぐ分を併合時に数える。
  • なぜ漏れも重複もないか。 半分全列挙では、元の対象と左右の組の対応を確認する。分割統治では、各対象をどの再帰呼出しが担当するかを定め、子の返す情報だけで親の仕事を処理できることを確かめる。

二択が nn 回ある半分全列挙では、左右の列挙数を近づけると大きい側を抑えられる。片側を整列し、他方の各候補について二分探索するなら、均等分割で時間は O(n2⌈n/2⌉)O(n2^{\lceil n/2\rceil})、入力と列挙結果を含む空間は O(n+2⌈n/2⌉)O(n+2^{\lceil n/2\rceil}) になる。実際には一候補の生成や比較にかかる費用も必要で、長い盤面や文字列を扱うならその長さも数える。

一方、長さ nn の列をほぼ半分ずつに分け、合計 O(n)O(n) で合成する分割統治では、同じ深さにある区間の長さの合計が nn になる。深さは O(log⁡n)O(\log n) なので、全体は O(nlog⁡n)O(n\log n) 時間になる。転倒数の例では、入力・併合用配列と再帰スタックを合わせて O(n)O(n) 空間で実行できる。合成のために全要素対を調べるならこの評価は使えず、分割が偏る場合も深さを数え直す。

分け方を選ぶための問い

全選択は多いが半分ずつなら列挙でき、片側から相手の条件を簡単に書けるなら、半分全列挙へ進もう。ABC271 Fでは経路を途中のマスで分け、位置とXORを照合する。ABC326 Fでは移動を軸ごとに整理してから、符号の選択を分ける。「入力の中央」が適切な分割とは限らない。

同じ形の小問題が現れ、その答えや要約から親を安く処理できるなら、再帰分割・分割統治を考える。ABC413 Eでは区間内で作れる最小の列を返し、ABC426 Gでは中央をまたぐ問い合わせをその場で処理する。子の答えを単純に足す場合に限られない。

両者は組み合わせることもできる。再帰の一段で左右の候補を照合してもよい。手法名を決める前に、分けた後に必要な情報、漏れと重複のない対応、合成も含めた計算量の三つを説明できるようにしよう。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。探索空間を独立に分ける場合と、再帰的な小問題へ分ける場合を区別する入口。

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

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-divide-enumeration

前提と範囲

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

直接の前提単元: なし。

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

このUnitでは扱わないもの

  • 候補数を制約・生成パラメータ・有限caseで直接界して全列挙する探索、軽重分類による償却解析、および入力木・trie・区間DPの構造をそのまま辿るだけの再帰。

根拠