C++でXORの合計値の最大値を求めるプログラム（貪欲法による解説）

問題概要

N個の要素を持つ配列 A と、ある整数 K が与えられます。0 以上 K 以下の範囲にある整数 X に対して、次のような関数 f(X) を定義します。

f(X) = (X XOR A[1]) + (X XOR A[2]) + ... + (X XOR A[N])

このとき、f(X) が取り得る最大値を求めるのがこの問題の目的です。

たとえば、入力が K = 7、A = [1, 6, 3] の場合を考えてみましょう。X = 4 を選ぶと、
f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14
となり、これが最大値となります。

解き方（アルゴリズム）

この問題は、各ビット位置に着目した貪欲法（グリーディ法）で効率的に解くことができます。上位ビットから順に処理しながら、X の各ビットを 1 にすべきかどうかを判定し、合計値を最大化していきます。

具体的には、以下の手順に従います。

1. 配列 A のサイズを n とします。
2. i = 45 から 0 まで、ビット位置を降順に処理します。
3. p = 2^i として、配列内でそのビットが立っている要素の個数 m を数えます。
4. これまでに確定した X の値 o に p を加えても K を超えない場合は、X の該当ビットを 1 にできるか検討します。ビットを立てたほうが合計が大きくなる（m < n - m の場合）なら、X のビットを立てます。
5. 各ビットの寄与分 p × m を答え d に加算していきます。

n := size of A
for initialize i := 45, when i >= 0, update (decrease i by 1), do:
   p := 2^i
   m := 0
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if A[j] AND p is non-zero, then:
         (increase m by 1)
   if o + p <= k, then:
      if m < n - m, then:
         m := n - m
         o := o + p
   d := d + p * m
return d

C++実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

long solve(int k, vector<int> A){
   long n = A.size(), d = 0, m, p, o = 0;
   for (long i = 45; i >= 0; i--){
      p = pow(2, i);
      m = 0;
      for (int j = 0; j < n; j++){
         if (A[j] & p)
            m++;
      }
      if (o + p <= k){
         if (m < n - m){
            m = n - m;
            o += p;
         }
      }
      d += p * m;
   }
   return d;
}
int main(){
   int K = 7;
   vector<int> A = { 1, 6, 3 };
   cout << solve(K, A) << endl;
}

入力

7, { 1, 6, 3 }

出力

14

まとめ

XORの性質を利用すると、各ビットを独立に評価できるため、ビット数 × N の計算量で最大値を求められます。XORを含む最適化問題では、ビット単位の貪欲法が有効なケースが多いため、考え方を覚えておくと競技プログラミングなどで役立ちます。