C++でサイズkの部分配列における最大XOR値を効率的に求める方法

この問題では、n個の要素からなる配列 arr[] と整数 k が与えられます。求めるのは、サイズkの部分配列（サブアレイ）の中で、要素全体のXOR値が最大になるものです。

入力例

arr[] = {3, 1, 6, 2, 7, 9}
k = 3

出力例

12

説明

サイズkのすべての部分配列と、その要素のXOR値は以下のようになります。

{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12

この中で最大のXOR値は 12 であり、これが答えとなります。

解法アプローチ

シンプルな解法：二重ループ

最も単純な方法は、二重ループを使うことです。外側のループで配列を走査し、内側のループで各部分配列の全要素のXORを計算します。そして、得られたXOR値のうち最大のものを返します。

この方法でも正しい結果は得られますが、計算量はO(n×k)となり、配列が大きい場合は非効率です。そこで、より優れたアプローチを紹介します。

効率的な解法：スライディングウィンドウ

XORには x ^ a ^ x = a という重要な性質があります。同じ値を2回XORすると元に戻るという性質で、これを利用すると「要素の削除」が可能になります。

まず、インデックス0から始まるサイズkの部分配列のXOR値を計算します。次に、配列を先頭から順に走査しながら、以下の操作を繰り返します。

1. 現在のXOR値に対して XOR ^ arr[i - k] を実行し、ウィンドウの先頭の要素を取り除きます。これにより、直前のインデックス+1から現在のインデックス-1までの部分配列のXOR値が得られます。
2. 続いて XOR ^ arr[i] を実行し、新しい要素をウィンドウに追加して、現在の部分配列のXOR値を更新します。

この操作を毎回行いながら、すべてのXOR値の中から最大値を見つけて返します。この方法なら計算量はO(n)に抑えられ、非常に効率的です。

ソリューションの実装例

#include<iostream>
using namespace std;

int findMaxSubArrayXOR(int arr[], int n, int k) {
    int currentXORVal = 0;
    // 最初のk個の要素のXORを計算
    for (int i = 0; i < k; i++)
        currentXORVal = currentXORVal ^ arr[i];
    int maxXor = currentXORVal;
    // スライディングウィンドウで残りの部分配列を処理
    for (int i = k; i < n; i++) {
        currentXORVal = currentXORVal ^ arr[i - k]; // 先頭の要素を除去
        currentXORVal = currentXORVal ^ arr[i];     // 新しい要素を追加
        maxXor = max(maxXor, currentXORVal);
    }
    return maxXor;
}

int main() {
    int arr[] = {3, 1, 6, 2, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "サイズ " << k << " の部分配列の最大XOR値は "
         << findMaxSubArrayXOR(arr, n, k);
    return 0;
}

出力

サイズ 3 の部分配列の最大XOR値は 12

まとめ

XORの性質「x ^ a ^ x = a」を活用したスライディングウィンドウ手法を使うことで、サイズkの部分配列の最大XOR値をO(n)の時間計算量で効率的に求めることができます。二重ループによるO(n×k)の素朴な解法と比べ、大規模な配列に対しても高速に動作するのが大きな利点です。