bitwise greedyによるmask最適化

概要

非負整数を小さくしたいときは、下位の桁を工夫するより先に、上位の1を0にできるか考える。ただし、一つの桁を改善した後も、それまでに決めた桁をすべて満たす解が残っていなければならない。上位から可否を確かめて桁を決めるのがbit貪欲法である。

各bitを0または1で指定した整数表現を mask(ビットマスク)、上位から既に確定した桁の並びを prefix(接頭辞) と呼ぶ。feasibility oracle(実現可能性の判定器) は、「指定した条件を満たす解が少なくとも一つ存在するか」を答える手続きである。最適解そのものを求めず、存在の判定へ問題を分ける。

考え方

数値の大小と、1のbitの包含は別の順序

二進数を3桁で書くと、3=(011)23=(011)_2、4=(100)24=(100)_2 である。数値としては3の方が小さいが、3の立っているbitは4に一つも含まれない。「数値以下」と「許したbitだけを使う」は異なる条件である。

一方、数値の比較は上位から最初に違う桁で決まる。下位から0始まりで kk 桁目の重みは 2k2^k であり、それより下の桁の重みの総和は 2k−12^k-1 しかない。そのため、同じ上位prefixのもとで kk 桁目を1から0へ変えられれば、下位がすべて1になっても数値は小さくなる。これが上位から決める理由である。

OR最小化を「許したbitだけで到達できるか」へ変える

ABC408 Eでは、無向グラフの始点から終点への経路について、辺ラベルのビット単位ORを最小化する。ORは、どれか一つの辺に立っているbitをすべて集める演算である。

mask MM の1を「使ってよいbit」と定める。辺ラベル ww のすべての1が MM に含まれる条件は

wORM=Mw\mathbin{\mathrm{OR}}M=M

である。この辺だけを残し、始点から終点へ到達できるかを判定器とする。許可辺だけの経路ならORも MM に含まれ、逆にORが MM に含まれる経路では全辺が許可されるので、この判定は必要十分である。探索で得た道筋に同じ頂点の再訪があっても、その間を取り除けば許可辺だけの単純パスにできる。

この判定は、許可bitを増やす方向には真を保つ。同じ経路を使えるからである。しかし、数値を増やす方向に単調とは限らない。ラベル3の辺しかない二頂点のグラフなら、mask 3は真、mask 4は偽となる。従って、この判定を数値上の通常の二分探索へそのまま渡すことはできない。

未確定の下位bitを自由にして、上位から0を試す

説明用に、頂点1から3へ次の二通りで進める小グラフを考える。

  • 頂点1と2の間のラベルは 2=(010)22=(010)_2、頂点2と3の間は 1=(001)21=(001)_2。この経路のORは 3=(011)23=(011)_2。
  • 頂点1と3の間のラベルは 4=(100)24=(100)_2。この経路のORは 4=(100)24=(100)_2。

最初は全bitを許す M=(111)2M=(111)_2 とする。ここから上位bitを一つずつ仮に消し、到達できれば消去を採用し、できなければ元へ戻す。

調べる桁試すmask判定の理由採用後のmask
4の位011頂点2を経由して到達できる011
2の位001頂点1から出られない011
1の位010頂点3へ到達できない011

答えは3である。4の位を消す判定で 000 を試すと、下位bitも同時に禁止することになり、存在する経路 011 を見逃す。確定した0だけを禁止し、未確定の下位bitはすべて1のまま許すことで、「下位をうまく選べば、この上位の0を実現できるか」を調べられる。

また、各bitを最初の 111 から独立に消してはならない。上の例では4の位は経由路で消せ、2の位も1の位も直通路で消せる。しかし三つを同時に消した 000 の経路はない。判定ごとに違う解が存在するだけでは、全条件を同時に満たす解の存在は保証されない。前の決定を次のmaskへ必ず引き継ぐ。

残っている解の集合から、貪欲法を正当化する

一般の整数値の最小化では、「確定済みprefixに続けて次の桁を0にし、残りを自由に選べる解があるか」を判定する。あれば0、なければ1に確定する。初めに解が一つ以上あると分かっていれば、毎回、確定済みprefixを持つ解が存在するという不変条件を保てる。

0を選べるときは、そのprefixを持つどの値も、同じ上位prefixで次の桁が1の値より小さい。0を選べないときは、残る解がすべて1なので、その桁を1にしても候補を失わない。従って上位からの帰納法で、最小値を持つ解を残したまま全桁が確定する。最大化なら、同じ論証で先に1を試す。

ORの許可maskは、1の桁を「実際に使う」とは要求しない。この点も確定済みprefixとの同値性を確認する。過去に消せなかった桁については、その時点の候補にその桁が0の解は存在しなかった。その後は許可bitを減らすだけなので、0の解が新しく現れることはない。採用済みの0と、消去に失敗して残した1の両方が、残る全解の上位prefixと一致する。

最後まで到達可能性を保つため、終了時にも許可辺だけの経路が存在する。もしそのORが最終maskのある1を使わないなら、その桁は処理時にも消せたはずである。従って最終maskは実際に実現するOR値であり、上の帰納法から数値として最小となる。

成立条件と計算量

必要なのは、値を表せる有限のbit数、初めの解の存在、そして「過去の決定をすべて保ち、下位を自由にした存在判定」である。OR以外に使う場合も、「必要なbitを含む」「許したbitだけを使う」のどちらを判定しているかを明確にし、その条件が意図するprefixの判定と同値かを示す。

bit数を BB、判定費用を TT とすると、探索時間は O(BT)O(BT) で、前処理があれば別に加える。ABC408 Eでは 0≤w<2300\leq w<2^{30} なので、全30bitが1のmaskから始める。元のグラフが連結であるため、この初期maskは必ず実現可能である。

頂点数 NN、辺数 EE とし、各maskで許可辺だけのDFS/BFSを行えば、一判定 O(N+E)O(N+E)、全体 O(B(N+E))O(B(N+E)) 時間・O(N+E)O(N+E) 空間となる。DSUを毎回初期化して許可辺を結ぶ方法でも判定でき、時間は全体で O(B(N+E)α(N))O(B(N+E)\alpha(N)) と評価できる。α\alpha はDSUの償却計算量に現れる逆Ackermann関数である。maskを変えると禁止される辺も変わるので、前の判定の連結情報をそのまま使い回さない。

問題へ進むときは、bit演算の書き方だけでなく、判定器の必要十分性、未確定桁の自由さ、候補集合を空にしない更新の三つを確認しよう。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。上位bitの優先性と単調な可否判定を組み合わせてmaskを決める。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bitwise-greedy-feasibility

bitwise greedyによるmask最適化

習得する技能

  • 上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: なし。

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

上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • bitwise greedyによるmask最適化の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠