【C++】配列内のすべてのトリプレット（3要素の組み合わせ）におけるXORの最大値を求める方法

この問題では、整数の配列が与えられます。求めるのは、配列から選んだ3つの要素（トリプレット）の組み合わせすべての中で、XOR（排他的論理和）の値が最大になるものです。

問題の例

具体的な例を使って問題を確認してみましょう。

入力： array = {5, 6, 1, 2}

出力： 6

説明：

考えられるすべてのトリプレットとそのXOR値：
5 ^ 6 ^ 1 = 2
5 ^ 6 ^ 2 = 1
5 ^ 1 ^ 2 = 6
6 ^ 1 ^ 2 = 5

この中で最も大きいXORの値は 6（5 ^ 1 ^ 2）となるため、答えは 6 になります。

解法のアプローチ

最も単純な方法は、考えられるすべてのトリプレットのXORを総当たりで計算し、その最大値を出力することです。しかし、配列の要素数が非常に大きい場合、この方法は計算量が膨大になり、実用的ではありません。

そこで、より効率的に最大XORを求めるために、次の手順でアルゴリズムを構成します。

1. まず、配列内のすべてのペア（2要素）のXOR値を計算し、重複を除いてセット（set）に格納します。
2. 次に、セットに含まれる各XOR値と、配列の各要素とのXORを計算します。
3. 得られた値の中で最大のものを答えとして返します。

このようにペアのXORを事前にセットへまとめておくことで、同じXOR値の重複計算を避けることができ、素朴な全トリプレット走査よりも効率よく処理できます。

C++での実装例

上記の解法を実装したプログラムがこちらです。

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

int MaxTripletXor(int n, int a[]) {
    // すべてのペアのXOR値をセットに格納
    set<int> XORpair;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            XORpair.insert(a[i] ^ a[j]);
        }
    }

    // セット内の各値と配列の各要素とのXORの最大値を求める
    int maxXOR = 0;
    for (auto i : XORpair) {
        for (int j = 0; j < n; j++) {
            maxXOR = max(maxXOR, i ^ a[j]);
        }
    }
    return maxXOR;
}

int main() {
    int matrix[] = {1, 2, 3, 5, 7};
    int n = sizeof(matrix) / sizeof(matrix[0]);
    cout << "The maximum XOR sum triplets is " << MaxTripletXor(n, matrix);
    return 0;
}

実行結果

The maximum XOR sum triplets is 7

コードの解説

• XORpair（セット）： 配列内の全ペア a[i] ^ a[j] の結果を格納します。std::set を使うことで、重複するXOR値が自動的に排除されます。
• 第2ループ： セット内の各値と配列の各要素をXORし、これまでの最大値（maxXOR）より大きければ更新します。
• 戻り値： 最終的な maxXOR が、すべてのトリプレットの中で最大のXOR値となります。

このサンプルでは配列 {1, 2, 3, 5, 7} を使用しており、最大のトリプレットXORとして 7 が出力されます。