C++でビットの入れ替えによりXORが0になる部分配列の個数を求める方法

問題概要

整数値を含む配列 Arr[] が与えられます。このとき、XOR（排他的論理和）が 0 になる部分配列の個数を最大化することが目標です。ただし、任意の部分配列については、その構成要素同士でビットを何度でも入れ替えられるものとします。

制約：1 ≤ Arr[i] ≤ 10¹⁸

ビットの入れ替えによってある部分配列の XOR を 0 にするためには、次の 2 つの条件を満たす必要があります。

• 区間 left ～ right に含まれるセットビット（値が 1 になっているビット）の総数が偶数であること。

• 任意の区間において、セットビット数の合計が「区間内で最もセットビット数が多い要素」のセットビット数の 2 倍以上であること（sum ≥ 2 × max）。

具体的な入出力シナリオを見てみましょう。

入力 − Arr[] = { 1, 2, 5, 4 }

出力 −

条件 1 のみを満たす部分配列の個数：4

両方の条件を満たす部分配列の個数：3

入力 − Arr[] = { 3, 7, 2, 9 }

出力 −

条件 1 のみを満たす部分配列の個数：6

両方の条件を満たす部分配列の個数：3

プログラムで使用するアプローチ

このアプローチでは、ビットの入れ替えによって部分配列の XOR を 0 にするには、「区間内のセットビットの総数が偶数であること」と「セットビット数の合計が最大値の 2 倍以上であること」という 2 つの条件が必要である点に着目します。

• 入力配列 Arr[] を受け取り、その長さを求めます。

• 関数 removeSubarr(int arr[], int len) は、条件 2 を満たさない部分配列の個数を返します。

• カウントの初期値を 0 に設定します。

• for ループで配列を走査しながら、変数 sum と maxVal を管理します。

• 別の for ループで、各開始位置から最大 60 個の範囲だけ走査します。10¹⁸ 未満の整数のセットビット数は最大でも 60 個程度なので、60 個を超える要素を含む区間では条件 2 が成立しなくなることはあり得ないためです。

• 要素を sum に加算し、maxVal を最大値で更新します。

• sum が偶数で、かつ 2 × maxVal > sum の場合は条件 2 を満たしていないため、カウントを 1 増やします。

• 両方のループが終了したらカウントを返します。

• 関数 findSubarrays(int arr1[], int len1) は、入力配列とその長さを受け取り、前述の両方の条件を満たす部分配列の個数を返します。

• 条件 1 のみを満たす部分配列の個数を求めるために、累積和（プレフィックスサム）配列を用意します。

• for ループで配列を走査し、各要素を __builtin_popcountll(arr1[i])、つまりその要素のセットビット数に置き換えます。

• for ループで prefix 配列を構築し、prefix[i] = prefix[i] + prefix[i - 1] とします（最初の要素を除く）。

• prefix 配列の中の奇数と偶数の個数をそれぞれ数えます。

• tmp1 = (奇数の個数 × (奇数の個数 − 1)) / 2、tmp2 = (偶数の個数 × (偶数の個数 − 1)) / 2 とし、result をその合計とします。

• この result が、条件 1 のみを満たす部分配列の個数になります。

• result を出力します。

• 続いて result = result − removeSubarr(arr1, len1) として更新します。

• これで result には、両方の条件を満たす部分配列の個数が格納されます。

• 再度 result を出力します。

アルゴリズムのポイント

条件 1 で「セットビットの総数が偶数」が必要なのは、XOR を 0 にするには各ビット位置の 1 の個数を偶数に揃える必要があるからです。また条件 2 が必要なのは、ある 1 つの要素が他のすべての要素のセットビット数の合計よりも多くのビットを持っている場合、その余剰分を他の要素とペアにできず、全要素を偶数個にできなくなってしまうためです。この 2 つの条件を組み合わせることで、ビットの入れ替えによって実際に XOR を 0 にできる部分配列だけを正確に数えられます。

なお、内側のループが最大 60 回しか回らないため、計算量は O(N × 60) ≒ O(N) となり、非常に効率的なアルゴリズムです。

コード例

#include <bits/stdc++.h>
using namespace std;
// 条件2を満たさない部分配列の個数を数える関数
int removeSubarr(int arr[], int len){
    int count = 0;
    for (int i = 0; i < len; i++){
        int sum = 0;
        int maxVal = 0;

        for (int j = i; j < min(len, i + 60); j++){
            sum = sum + arr[j];
            maxVal = arr[j] > maxVal ? arr[j]: maxVal;

            if (sum % 2 == 0){
                if( 2 * maxVal > sum)
                    { count++; }
            }
        }
    }
    return count;
}
int findSubarrays(int arr1[], int len1){
    int prefix[len1];
    int oddcount, evencount;
    int result;
    for (int i = 0; i < len1; i++)
    { arr1[i] = __builtin_popcountll(arr1[i]); }

    for (int i = 0; i < len1; i++){
        prefix[i] = arr1[i];
        if (i != 0)
            { prefix[i] = prefix[i] + prefix[i - 1]; }
        }
        oddcount = evencount = 0;
        for (int i = 0; i < len1; i++){
            if (prefix[i] % 2 == 0)
                { evencount = evencount +1; }
            else
                { oddcount = oddcount +1; }

        }
        evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3