上位bitの支配関係によるXOR minimax

概要

最大XORを最小にする共通maskを求めるとき、最上位bitで値を二群へ分ける。一群だけならそのbitを相殺し、両群なら最大値のそのbitは必ず1なので、どちらの群を最大側にするかを再帰的に比較する。

考え方

max_i(x XOR a_i)を最小化するには、最上位の未確定bitで値集合を二分する。両側があれば最大値にそのbitが立ち、xの選択に応じた片側の下位問題へ進む。

下位b+1 bitでの最適値をF(C,b)とし、F(C,−1)=0。bit bで分けたC0,C1の一方だけが非空なら、maskのそのbitを同じ値にして F=F(非空側,b−1)。両方非空なら F=2^b+min(F(C0,b−1),F(C1,b−1))。maskのbitを1にするとC0が最大側、0にするとC1が最大側になる。最大側の値は必ず2^b以上、他方は2^b未満なので、他方の下位bitを最適化へ混ぜない。小さい再帰値を選んだ側とbitを記録すればmaskも復元できる。同じ深さでは各入力値が一群だけに属すので総走査O(NB)となる。

成立条件と計算量

Trieやbit再帰でO(NB)の典型になる。全値が同じ側なら上位bitを消して進める。目的が最大値であることが再帰式の根拠で、XOR和や任意のmatchingへ同じ式を適用しない。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。上位bitが最大値を支配することを使い、二群への再帰とminimaxを導く。

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

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bitwise-minimax-partition

上位bitの支配関係によるXOR minimax

習得する技能

  • 最大XORを最小にする共通maskを求めるとき、最上位bitで値を二群へ分ける。一群だけならそのbitを相殺し、両群なら最大値のそのbitは必ず1なので、どちらの群を最大側にするかを再帰的に比較する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: なし。

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

最大XORを最小にする共通maskを求めるとき、最上位bitで値を二群へ分ける。一群だけならそのbitを相殺し、両群なら最大値のそのbitは必ず1なので、どちらの群を最大側にするかを再帰的に比較する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 上位bitの支配関係によるXOR minimaxの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠