C++で配列の指定範囲とのXOR合計が最大となる数を見つける方法

この記事では、配列と複数のクエリが与えられる問題を解きます。各クエリでは区間（L, R）が指定され、その区間内の各要素とxとのXORの合計が最大になるような数xを見つける必要があります。具体例を見てみましょう。

入力 : A = {20, 11, 18, 2, 13}
3つのクエリを (L, R) ペアとして与える
1 3
3 5
2 4
出力 : 2147483629
2147483645
2147483645

この問題では、まず各ビット位置ごとに「1」が出現する回数の累積和（プレフィックスカウント）を求めておきます。事前に1の個数を計算していれば、クエリで指定された区間L〜Rに含まれる1の個数は、「Rまでの累積値」から「L−1までの累積値」を引くだけで簡単に求められます。

解法のアプローチ

XORの合計を最大化するためには、XOR結果のなるべく多くのビットを1にする必要があります。そこで各ビットについて、区間内で1の方が0より多い場合は、xのそのビットを0にリセットします。その理由は、そのビットが1である要素が多数派を占めているため、x側を0にすることでXOR結果のそのビットが多数派において1となり、結果として答えを最大化できるからです。

コード例

上記アプローチのC++コード

#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // 累積和用の配列
void prefix_bit(int A[], int n){ // 各ビットの1の個数を累積カウント
    for (int j = 0; j < 32; j++) // 0番目のカウントを0とし、累積配列はインデックス1から開始
        prefix[0][j] = 0;
    for (int i = 1; i <= n; i++){ // 累積配列の構築
        int a = A[i - 1]; // i番目の要素
        for (int j = 0; j < 32; j++){ // 数値は2^32未満なのでビット0〜31を走査
            int x = 1 << j; // ビットの走査
            if (a & x) // このビットが1なら前のカウント+1
                prefix[i][j] = 1 + prefix[i - 1][j];
            else
                prefix[i][j] = prefix[i - 1][j];
        }
    }
}
int maximum_num(int l, int r){
    int numberofbits = r - l + 1; // 区間内の要素数＝判定対象のビット数
    int X = MAX; // すべてのビットが1となる最大値を初期値とする
    // 各ビットを走査
    for (int i = 0; i < 31; i++){
        int x = prefix[r][i] - prefix[l - 1][i]; // 区間内のセットビット数を計算
        if (x >= numberofbits - x){ // 1の数が0の数以上の場合
            int currentbit = 1 << i; // 反転対象のビット
            X = X ^ currentbit; // xのそのビットを1から0へ反転
        }
    }
    return X; // 答えを返す
}
int main(){
    int n = 5, q = 3; // 配列の要素数とクエリの数
    int A[] = { 210, 11, 48, 22, 133 }; // 配列の要素
    int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // クエリの区間
    prefix_bit(A, n); // ビット累積配列の作成
    for (int i = 0; i < q; i++)
       cout << maximum_num(L[i], R[i]) << "\n";
    return 0;
}

出力

2147483629
2147483647
2147483629

コードの解説

このアプローチでは、まず各ビットごとに1の出現回数の累積和を計算します。この累積和を求めてしまえば、最大の難所であった「クエリごとの区間走査」は不要になります。つまり、毎回区間を一つずつ走査する代わりに、累積配列から即座に計算できるのです。基本となるロジックは次のとおりです。区間内の各ビットについて、セットされている（1になっている）ビットの数とリセットされている（0になっている）ビットの数を求め、セットビットの数が多い位置を見つけたら、xのそのビットをリセットします。xは初期値として 2^31 − 1（すべてのビットが1）で初期化されているため、あとはxの該当ビットを反転させることで答えを導き出せます。

まとめ

このチュートリアルでは、配列の指定された区間とのXOR合計が最大になる数を見つける問題を解きました。さらに、この問題に対するC++プログラムと、それを解くための標準的なアプローチについても学びました。同じプログラムは、C、Java、Pythonなど他の言語でも実装可能です。このチュートリアルが皆さんの学習のお役に立てば幸いです。