候補数を界して全列挙・有限case分解する

概要

全探索を使えるかどうかは、入力の最大値だけでは決まらない。答えの候補を少数のパラメータで作れるなら、巨大な値域を順に調べる必要はない。また、候補が多くても、同じ種類の失敗を繰り返せないなら、成功までの処理回数を小さく抑えられる。

この単元では、何を一候補とし、何回処理するのかを証明してから列挙する考え方を学ぶ。候補の表現、漏れと重複、生成・判定の費用を一続きに考えることが目標である。

考え方

大きな答えを、小さな設計図から作る

十進表記で隣り合う桁の差が一定の整数を探すとしよう。例えば 246 や 975 が該当する。整数を1ずつ増やして検査すると、大きな答えにたどり着くまでの回数が問題になる。そこで、条件を検査する代わりに、条件を満たす数の作り方を考える。

3桁の数なら、最初の桁と桁の差を決めた時点で、残りの桁も決まる。

先頭差作る桁判定
222 → 4 → 6有効
9−29 → 7 → 5有効
7−67 → 1 → −5無効

最初の2行からは 246 と 975 が得られる。最後の行は、3桁目が0から9の範囲を外れるため捨てる。

一般に、桁数を ℓ\ell、先頭の桁を aa、桁の差を dd とすると、先頭を0番目とした jj 番目の桁は a+jda+jd である。先頭は1から9、それ以外は0から9でなければならない。差は広めに −9≤d≤9-9\leq d\leq9 としておけば、必要な場合をすべて含められる。

桁数の上限を DD と定められれば、試すパラメータの組は高々

D×9×19D\times9\times19

通りである。各組で桁を順に作り、範囲を外れたら捨て、完成した数が要求を満たすか調べる。

ここで必要なのは、範囲が小さいことに加えて、正解がその範囲に必ず入る理由である。ABC234 Eでは、与えられる整数は 101710^{17} 以下で、それ以上の等差数の最小値を求める。18桁の 111111111111111111 は必ず有効な上界になるため、18桁までを作れば足りる。18桁という打ち切りは、答えの上界から導いている。公式問題文・公式解説でも確認できる。

任意の有効な整数から桁数・先頭・差を取り出すと、列挙した組の一つに戻る。したがって漏れはない。一方、1桁の数は差を変えても同じ数になる。最小値の更新なら重複して調べても答えは変わらないが、異なる整数の個数を数えるなら、1桁だけ別に扱うなどの重複対策が必要になる。

桁を毎回作り直す実装では、一候補に最大 O(D)O(D) 時間かかり、全体は O(D2)O(D^2) 時間である。最良の候補だけを保持するなら全候補の保存は不要で、桁列を作業用に置く場合も追加空間は O(D)O(D) で済む。以降も、候補の数と一候補を作る費用は分けて数える。

選ぶ集合を、ビット列と一対一に対応させる

次に、3個の品物から好きなものを選ぶ場面を考える。品物の添字を0、1、2とし、費用を順に2、3、5、予算を5とする。各品物について「選ぶ・選ばない」を決めれば、選ぶ集合をすべて作れる。

各選択を二進数の1桁に対応させた整数を bitmask と呼ぶ。右端を品物0の桁とすると、全候補は次の8通りになる。

ビット列選ぶ添字費用予算内か
000空集合0はい
00102はい
01013はい
0110, 15はい
10025はい
1010, 27いいえ
1101, 28いいえ
1110, 1, 210いいえ

品物が NN 個なら、maskを0以上 2N2^N 未満の整数として走査する。添字 ii の品物を選ぶかは、実装では (mask >> i) & 1 で調べられる。各部分集合には一つのビット列が、各ビット列には一つの部分集合が対応するので、漏れも重複もない。空集合を含むことも、この対応から分かる。

各maskで全品物を調べるなら O(N2N)O(N2^N) 時間である。費用の入力配列に O(N)O(N) 空間を使い、候補の集合を整数だけで表すなら追加空間は O(1)O(1) で済む。ただし、これはmaskが定数個の機械語に収まる場合の評価である。実装言語の整数幅を超えるシフトや、符号付き整数の扱いにも注意する。

選んだ品物に共通する性質を調べたい場合も同じ表現が使える。例えば、品物0が対応できる曜日を月・水・金、品物1を水・金・日とすると、両方に共通する曜日は水・金である。各曜日にもビットを割り当てれば、集合の共通部分はビットごとのAND、和集合はORで求められる。

曜日の種類数を W=7W=7 とし、品物 ii の曜日集合を available[i] で表す。一つの選択maskを評価するときは、common を全曜日のビットが1の (1 << W) - 1 に初期化し、選んだ各品物について common &= available[i] と更新する。小例では、全曜日 → 月・水・金 → 水・金と絞られる。0で初期化すると、ANDを何度取っても空集合のままになる。

最後に立っているビットの個数を数える操作をpopcountといい、これで共通する曜日数が得られる。品物の選択に使う NN ビットと、曜日の性質に使う WW ビットは別の軸である。曜日集合が一語に収まるなら、全選択の共通部分も O(N2N)O(N2^N) 時間で計算できる。複数語にまたがる場合は、ANDの費用にも語数分を掛ける。空の選択では common は全曜日のままだが、この選択を答えへ含めるかは問題の定義で決める。

bitmaskは集合の表現方法であり、使うだけで探索が速くなるわけではない。全maskを評価すれば候補数は依然として 2N2^N である。ABC219 Eでは16領域の内外を選ぶため、この数が小さい。一方、領域の選び方が対応する堀を作れるかは別途判定する必要がある。公式解説の全探索も、この「生成と合法性の検査」の組合せである。

個数が決まっているなら、完成できる組だけを作る

5個から2個を選ぶなら、必要なのは 25=322^5=32 個の部分集合すべてではなく、(52)=10\binom52=10 個の組合せである。選んだ添字を小さい順に並べると、

(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)(0,1),(0,2),(0,3),(0,4), (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)

だけを生成すればよい。選ぶ順番を自由にすると (0,1) と (1,0) が同じ集合を表すが、添字を増加させれば各集合の表現が一意になる。

一般に、NN 個から KK 個を選ぶ途中で、すでに rr 個を選んでいるとする。次に選ぶ添字を ii とすると、その後には K−r−1K-r-1 個分の添字が必要である。添字の最大値が N−1N-1 なので、次の候補は

i≤N−(K−r)i\leq N-(K-r)

を満たすものだけにする。例えば5個から2個なら、最初に4を選ぶ枝は最初から作らない。以後の選択は直前の添字より大きい範囲に限り、KK 個になったら評価する。

この生成方法では、各途中状態が少なくとも一つの完成した組へ延長できる。深さごとに見ると、異なる途中状態の下にある完成形は重ならないため、途中状態も各深さで高々 (NK)\binom NK 個である。したがって生成全体は、根を含めて O((K+1)(NK))O((K+1)\binom NK) 時間で抑えられる。完成時の判定に CC 時間かかるなら、その費用 O(C(NK))O(C\binom NK) も加える。入力を保存する O(N)O(N) に加え、選択列と再帰スタックは O(K)O(K) 空間である。K=0K=0 なら空集合を一度評価し、K>NK>N なら候補はない。

ABC386 Eのように (NK)\binom NK が小さいという制約は、この生成を直接促している。特に KK が NN に近いなら、選ばない側の N−KN-K 個を作ると状態更新も軽くできる。XORでは全要素のXORから選ばない要素のXORを再び取ると、選ぶ側の値が得られる。ただし、補集合を列挙するには、元の候補の評価値を補集合から復元できることも必要である。公式解説ではこの対応を用いている。

全候補が多くても、失敗を記録する場所が少ない

「二重ループの回数を全部足すと大きい」だけでは、早期終了する探索を正しく評価できない。成功するまでに、何回失敗できるかを考えよう。

二部グラフで、片側に3頂点 x,y,zx,y,z があるとする。反対側の各頂点について、隣接する2頂点の組を調べる。組 {x,y}\{x,y\} が初めて出たら、それを見つけた頂点を記録する。同じ組が別の頂点から再び出れば、4頂点で長さ4のサイクルができる。

調べる頂点隣接頂点の組記録と判断
aa{x,y}\{x,y\}初出なので aa を記録
bb{x,z}\{x,z\}初出なので bb を記録
cc{x,y}\{x,y\}aa と cc が共通の2頂点を持つので成功

この時点で a→x→c→y→aa\to x\to c\to y\to a というサイクルが復元できる。記録先は {x,y},{x,z},{y,z}\{x,y\},\{x,z\},\{y,z\} の3個しかない。成功しない処理は必ず空の記録先を一つ埋めるので、失敗は高々3回、成功するなら遅くとも4回目である。衝突が起こらないまま全候補を調べ終えた場合は、「存在しない」と判定する。

ABC260 Fでは、一方の頂点数に T≤3000T\leq3000 という小さな上限がある。こちらの頂点対を記録先にすると、その数は B=(T2)B=\binom T2 個になる。反対側の頂点を一つずつ処理し、各隣接リスト内で添字の異なる順不同の組を一度ずつ調べる。同じ頂点から同じ組を二度作らないため、記録済みの組を見つけたときは必ず別の頂点による発見になる。

探索中は「各記録には、その組の両頂点に隣接する、処理済みの頂点が一つ入っている」という不変条件を保つ。未記録なら登録し、記録済みならサイクルを出力して終了する。成功せずに全頂点を調べ終えたなら、共通の2頂点を持つ頂点対は存在せず、サイクルも存在しない。

組を調べる回数は高々 B+1B+1 回である。反対側の頂点数を SS、辺数を MM とすると、隣接リストの構築・外側の走査・記録配列の初期化も含め、時間は O(S+T+M+T2)O(S+T+M+T^2)、空間も O(S+T+M+T2)O(S+T+M+T^2) になる。公式解説の鳩ノ巣原理は、この失敗回数の評価に対応する。

この上界は、発見したら探索全体を止めることに依存する。すべてのサイクルを数える要求では、同じ記録先が何度現れても続ける必要があり、同じ計算量とは言えない。

成立条件と計算量

列挙の設計では、まず正解を含む候補集合を定め、次にその生成方法の漏れ・重複を確認する。そのうえで、実際に処理する候補数と一候補の費用を掛け合わせる。前処理に PP 時間、実際に処理する候補が QQ 個、生成と判定の合計が一候補あたり最大 CC 時間なら、全体の時間は O(P+QC)O(P+QC) である。候補を全保存するか、その場で評価して捨てるかによって空間も変わる。

上界を出す根拠は問題によって異なる。少数の変数が独立に動くなら範囲の大きさを掛け、選ぶ個数が固定なら組合せを数える。配置を有限の場合に分けるなら、どの合法配置も少なくとも一つの場合に入ることを示す。場合が重なっても最適値を取るだけなら構わないが、計数では重複の補正が必要になる。

探索を打ち切る場合は、打ち切り前の処理回数を別に証明する。「早く見つかりそう」「枝刈りが効きそう」は最悪計算量の根拠にならない。失敗を未使用の記録先に対応付けられるか、数えた候補数だけで要求が確定するかを調べる。

bitmask列挙は完成した集合を表す方法であり、バックトラックは部分的な選択を伸ばして戻す方法である。後者でも使用集合をbitmaskで持てる。さらに枝刈りは、ある途中状態から必要な答えが出ないと証明して、その先を調べない判断を指す。表現・探索手順・候補を捨てる根拠は、それぞれ別に選ぶ。

主配置問題へ進む際は、ABC234 Eで「巨大な値を決定する小さなパラメータ」、ABC328 Eで「木を作る辺数を固定した組合せ」、ABC219 Eで「全maskの生成と形状の判定」を確認するとよい。ABC260 Fでは候補総数を数える発想から一歩進め、失敗を記録する場所を探す。復習では、ループの形を覚える前に「何の個数を上から抑えたのか」を説明し直そう。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。制約から候補数を見積もり、成功までの探索回数を界する考え方を学ぶ。

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

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

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

習得する技能

  • 条件を満たす対象を決定する量を見つけ、列挙範囲の上界と網羅性を説明する。
  • 部分集合のbitmask表現と、個数を固定した組合せの生成を使い分ける。
  • 早期終了までの失敗を、有限個の記録先へ対応付けて数える。
  • 候補数だけでなく、前処理・生成・判定・保存を含めて実行可能性を判断する。

前提と範囲

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

直接の前提単元: なし。

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

候補総数を直接界す全列挙と、鳩ノ巣原理で成功前の失敗回数だけを界す探索を分け、実際に処理する回数を証明する。

このUnitでは扱わないもの

  • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

根拠