C++で4つの配列からXORがxと等しくなる4つ組（クワドループル）をすべて数える方法

このチュートリアルでは、4つの配列から1つずつ要素を選んだとき、そのXOR（排他的論理和）が指定した値xと等しくなる組み合わせ（4つ組）の個数を求めるプログラムについて解説します。

具体的には、4つの配列と値xが与えられ、各配列から1つずつ要素を選んで作れるすべての組み合わせの中から、XORの結果がxと一致するものを数えるのが目的です。

解き方のアプローチ

最もシンプルな方法は、4重のループを使った総当たり（ブルートフォース）です。4つの配列から選べる要素の組み合わせをすべて列挙し、それぞれについてXORを計算します。結果がxと等しければカウントを1つ増やし、最終的なカウントを答えとして返します。

サンプルコード

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

// XORがxと等しくなる4つ組の個数を数える関数
int count_quad(int a[], int b[], int c[], int d[],
int x, int n){
    int count = 0;
    for (int i = 0 ; i < n ; i++)
        for (int j = 0 ; j < n ; j++)
            for (int k = 0 ; k < n ; k++)
                for (int l = 0 ; l < n ; l++)
                    if ((a[i] ^ b[j] ^ c[k] ^ d[l]) == x)
                        count++;
    return count;
}

int main(){
    int x = 3;
    int a[] = {0, 1};
    int b[] = {2, 0};
    int c[] = {0, 1};
    int d[] = {0, 1};
    int n = sizeof(a)/sizeof(a[0]);
    cout << count_quad(a, b, c, d, x, n) << endl;
    return 0;
}

出力

4

コードの解説

上記の例では、配列a、b、c、dから1つずつ要素を選んだとき、XORが3になる組み合わせは次の4通りです。

• (0, 2, 0, 1) → 0 ^ 2 ^ 0 ^ 1 = 3
• (0, 2, 1, 0) → 0 ^ 2 ^ 1 ^ 0 = 3
• (1, 2, 0, 0) → 1 ^ 2 ^ 0 ^ 0 = 3
• (1, 2, 1, 1) → 1 ^ 2 ^ 1 ^ 1 = 3

したがって、プログラムは4を出力します。

計算量と高速化のヒント

この総当たり法の時間計算量はO(n⁴)であり、配列のサイズが大きくなると実行時間が急激に増加します。実務では、ミート・イン・ザ・ミドル（Meet in the Middle）と呼ばれる手法を使うと効率化できます。まず配列aとbのすべてのペアのXORを計算してハッシュマップに記録し、次に配列cとdのペアのXORごとに「x ^ (c[k] ^ d[l])」という値がマップ内にいくつ存在するかを調べればよいのです。これにより、計算量をO(n²)まで大幅に削減できます。

まずは本記事のシンプルな実装でロジックを理解し、データ规模が大きいケースでは高速化手法の導入を検討するとよいでしょう。