C++でXORが0になる一意なトリプレットの個数を求める方法

はじめに

この記事では、ユニークな要素のみで構成された配列の中から、XOR（排他的論理和）の結果が0になる一意なトリプレット (x, y, z) の個数を数える方法について解説します。ここで「一意なトリプレット」とは、3つの要素がすべて異なる値であり、同じ3つの数字からなる組み合わせは1つとしてカウントするという意味です。

まずは、具体的な入力と出力の例を見てみましょう。

入力 : arr[ ] = { 5, 6, 7, 1, 3 }
出力 : 2
説明 : { 5, 6, 3 } と { 6, 7, 1 } の2つのトリプレットのXORが0になります。

入力 : arr[ ] = { 3, 6, 8, 1, 5, 4, 12 }
出力 : 3
説明 : { 3, 6, 5 }、{ 1, 5, 4 }、{ 4, 8, 12 } の3つのトリプレットのXORが0になります。

解決のためのアプローチ

XORの基本的な性質として、「同じ値同士のXORは必ず0になる」というものがあります。つまり、ある2つの値 a と b のXORを計算した結果 c が配列内に存在すれば、a ⊕ b ⊕ c = 0 が成立するため、(a, b, c) は条件を満たすトリプレットとなります。

この性質を利用すると、以下のような効率的なアプローチが考えられます。

1. 配列のすべての値をハッシュセットに登録しておきます。
2. 配列から選べるすべてのペア (i, j) について、そのXOR値を計算します。
3. 計算したXOR値がハッシュセット内に存在するかを確認します。ただし、XOR値がペアのどちらかの値と一致している場合は除外します（3つの要素がすべて異なる必要があるため）。
4. 条件を満たした場合にカウントを増やします。

なお、最終的な答えはカウントを3で割った値になります。これは、1つのトリプレット (a, b, c) に対して (a, b)、(b, c)、(a, c) の3通りのペアの組み合わせからそれぞれ1回ずつカウントされるためです。

C++での実装例

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

int main () {
    int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
    int n = sizeof (arr) / sizeof (arr[0]);
    int result;
    // ペアをカウントするための変数
    int count = 0;
    // ユニークな値を格納するセットを作成
    unordered_set < int >values;
    // セットに値を挿入
    for (int i = 0; i < n; i++)
        values.insert (arr[i]);

    // すべてのペアを走査してXORを計算
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            // ペア (i, j) のXORを求める
            int XR = arr[i] ^ arr[j];

            // ペアのXOR値が配列内に存在するか確認
            // （XOR値がペア自身の値と一致していないことも確認）
            if (values.find (XR) != values.end () && XR != arr[i] &&
                XR != arr[j])
                count++;
        }
    }
    // 結果を格納（各トリプレットは3回カウントされるため3で割る）
    result = count / 3;
    cout << "一意なトリプレットの数 : " << result;
    return 0;
}

出力

一意なトリプレットの数 : 3

コードの解説

• unordered_set<int> values; を作成し、配列内のユニークな値を高速に検索できるように格納しています。ハッシュセットを使うことで、存在確認を平均 O(1) で行えます。
• for() ループを使って values.insert(arr[i]) により、配列の全要素をセットに挿入します。
• 二重ループで配列内のすべてのペア (i, j) を走査し、それぞれのXOR値を計算します。
• 計算したXOR値がセット内に存在するかを検索し、存在する、かつXOR値がペアのどちらの値とも一致しない場合にカウントをインクリメントします。
• 最終結果は count / 3 として求めます。これは、1つのトリプレットがペアの組み合わせによって3回カウントされるためで、一意なトリプレットの数だけを得るために3で割っています。

このアルゴリズムの時間計算量は O(n²) です。すべてのペアを列挙するのに O(n²)、各ペアのセット検索は平均 O(1) であるためです。素朴に3つの要素のすべての組み合わせを試す O(n³) の方法よりも効率的です。

まとめ

この記事では、XORの値が0になるトリプレットの個数を求める問題について解説しました。「同じ値のXORは0になる」という性質を活かし、ハッシュセットを用いた効率的なアプローチで一意なトリプレットを見つける方法を紹介しました。また、実際に動作するC++プログラムも提示しました。なお、このプログラムはJava、C、Pythonなど他のプログラミング言語でも同様のロジックで実装可能です。本記事が皆さんの学習の一助となれば幸いです。