公式

E - チームの組み合わせ / Team Combinations 解説 by admin

gemini-3.5-flash-high

概要

2つのグループからそれぞれメンバーの部分集合を選び、それらのXOR和 \(X, Y\) が \(X + Y = S\) を満たすような部分集合の選び方の総数を求める問題です。 各グループの人数 \(N\) は最大で \(50\) と大きいですが、スキル値が \(2^{20}\) 未満と小さいことに着目し、線形基底（Linear Basis）を用いて探索空間を削減することで高速に解くことができます。

考察

1. 素朴なアプローチとその限界

各グループから部分集合を選ぶ方法はそれぞれ \(2^N\) 通りあります。\(N \le 50\) であるため、単純にすべての部分集合を全探索すると \(2^{50} \approx 1.1 \times 10^{15}\) 通りとなり、実行時間制限に間に合いません。

2. 値の範囲に着目する

一方で、各メンバーのスキル値は \(2^{20}\) 未満（約 \(10^6\)）と非常に小さいです。 XOR和として「実際に作り得る値」の種類数は、部分集合の総数 \(2^{50}\) よりもはるかに少なくなります。具体的には、作り得るXOR和は高々 \(2^{20}\) 通りしかありません。

ここで、「同じXOR和を作る部分集合の選び方は何通りあるか？」を効率よく求めることができれば、探索を大幅に高速化できます。これを可能にするのが線形基底（Linear Basis）です。

3. 線形基底によるアプローチ

\(N\) 個の要素からなる集合 \(A\) から、XOR演算における「基底」を構築します。 基底とは、集合 \(A\) の要素をいくつかXORすることによって作れるすべての値を、より少ない要素（高々 \(\log_2(\max A) \le 20\) 個）のXORで一意に表せるようにした部分集合のことです。

グループ1の基底のサイズ（基底に含まれる要素数）を \(d_A\) とします。このとき、以下の性質が成り立ちます。

  1. 作り得るユニークなXOR和の個数: 基底の要素の選び方は \(2^{d_A}\) 通りあり、これらはすべて異なるXOR和になります。
  2. 各XOR和の出現回数: 基底に含まれなかった \(N - d_A\) 個の要素（冗長な要素）の選び方は \(2^{N - d_A}\) 通りあります。これらの要素をどのように選んでも、それらのXOR和を打ち消す（または目的の値にする）ような基底の選び方が一意に存在します。 したがって、作り得る任意のXOR和 \(x\) に対して、それを実現する元の部分集合の選び方は一律で \(2^{N - d_A}\) 通り 存在します。

同様に、グループ2の基底のサイズを \(d_B\) とすると、作り得る任意のXOR和 \(y\) に対して、それを実現する部分集合の選び方は \(2^{N - d_B}\) 通り 存在します。

4. 問題の分解

以上の考察から、問題を以下のように分解できます。

  1. グループ1から作り得るユニークなXOR和の集合 \(V_A\)（サイズ \(2^{d_A}\)）を列挙する。
  2. グループ2から作り得るユニークなXOR和の集合 \(V_B\)（サイズ \(2^{d_B}\)）を列挙する。
  3. \(x \in V_A, y \in V_B\) かつ \(x + y = S\) を満たすユニークな値の組 \((x, y)\) の個数 \(C\) を求める。
  4. 各組 \((x, y)\) に対して、元の部分集合の選び方は \(2^{N - d_A} \times 2^{N - d_B} = 2^{2N - d_A - d_B}\) 通りあるため、最終的な答えは \(C \times 2^{2N - d_A - d_B}\) となります。

アルゴリズム

  1. 線形基底の構築: グループ1、グループ2のそれぞれについて、挿入操作を行いながら線形基底を構築します。 値が \(2^{20}\) 未満であるため、基底のサイズ \(d_A, d_B\) は高々 \(20\) になります。

  2. すべてのXOR和の列挙: 構築した基底の要素（高々 20 個）を全探索し、作り得るすべてのXOR和の集合 \(V_A, V_B\) を作成します。要素数は最大でも \(2^{20} \approx 10^6\) です。

  3. 条件を満たす組のカウント:

    • \(V_B\) の要素を高速に検索できるように、サイズ \(2^{20}\) の boolean 配列 in_VB を用意し、 \(V_B\) に含まれる要素のインデックスを true にします。
    • \(V_A\) の各要素 \(x\) について、 \(y = S - x\) を計算します。
    • \(0 \le y < 2^{20}\) かつ in_VB[y] が true である場合、条件を満たすためカウンター \(C\) を \(1\) 増やします。

  4. 答えの計算:

    • \(C = 0\) の場合は、条件を満たす組み合わせは存在しないため 0 を出力します。
    • \(C > 0\) の場合は、 \(C \times 2^{2N - d_A - d_B}\) を計算して出力します。これはビットシフト演算 C << (2 * N - d_A - d_B) を用いて高速に計算できます。

計算量

  • 時間計算量: \(O(N \log(\max A) + 2^{\log(\max A)})\)

    • 基底の構築: \(O(N \log(\max A))\)。 \(N \le 50\), \(\log(\max A) \le 20\) なので、最大でも \(50 \times 20 = 1000\) 回程度のループで完了します。
    • XOR和の列挙およびカウント: \(O(2^{d_A} + 2^{d_B})\)。 \(d_A, d_B \le 20\) より、最大でも約 \(2 \times 10^6\) 回の操作となり、1秒以内に十分実行可能です。

  • 空間計算量: \(O(2^{\log(\max A)})\)

    • \(V_A, V_B\) の要素を格納する配列、および存在判定用のテーブル in_VB のサイズは最大で \(2^{20}\)（約 \(10^6\)）です。C++の vector<bool> や通常の配列であれば数メガバイト程度であり、メモリ制限に対して非常に安全です。

実装のポイント

  • オーバーフローの防止: 最終的な答えは最大で \(2^{63}\) 未満になることが保証されていますが、C++の標準的な 32 ビット整数型（int）ではオーバーフローします。答えの計算やビットシフトの際には、unsigned long long や long long などの適切な 64 ビット整数型を使用する必要があります。

  • インデックスの境界チェック: \(y = S - x\) を計算した際、 \(y\) が負の値になったり、テーブルのサイズである \(2^{20}\) 以上になったりする可能性があるため、配列へのアクセス前に必ず境界チェック（y >= 0 && y < (1 << 20)）を行う必要があります。

    ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

// 線形基底を表す構造体
struct Basis {
    int basis[20];
    int sz = 0;
    Basis() {
        memset(basis, 0, sizeof(basis));
    }
    void insert(int x) {
        for (int i = 19; i >= 0; i--) {
            if ((x >> i) & 1) {
                if (!basis[i]) {
                    basis[i] = x;
                    sz++;
                    return;
                }
                x ^= basis[i];
            }
        }
    }
};

// 基底から生成されるすべてのXOR和を列挙する
vector<int> get_all_xor_sums(const Basis& b) {
    vector<int> active;
    for (int i = 0; i < 20; i++) {
        if (b.basis[i]) {
            active.push_back(b.basis[i]);
        }
    }
    vector<int> V;
    V.reserve(1 << active.size());
    V.push_back(0);
    for (int x : active) {
        int cur_sz = V.size();
        for (int i = 0; i < cur_sz; i++) {
            V.push_back(V[i] ^ x);
        }
    }
    return V;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, S;
    if (!(cin >> N >> S)) return 0;

    Basis basis_A, basis_B;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        basis_A.insert(a);
    }
    for (int i = 0; i < N; i++) {
        int b;
        cin >> b;
        basis_B.insert(b);
    }

    vector<int> V_A = get_all_xor_sums(basis_A);
    vector<int> V_B = get_all_xor_sums(basis_B);

    // V_B の要素を高速に判定するためのテーブル
    vector<bool> in_VB(1 << 20, false);
    for (int y : V_B) {
        in_VB[y] = true;
    }

    long long counter = 0;
    for (int x : V_A) {
        int y = S - x;
        if (y >= 0 && y < (1 << 20)) {
            if (in_VB[y]) {
                counter++;
            }
        }
    }

    if (counter == 0) {
        cout << 0 << "\n";
    } else {
        long long shift = 2LL * N - basis_A.sz - basis_B.sz;
        // 答えが 2^63 未満であるため、counter > 0 のとき shift <= 62 が保証される
        unsigned long long ans = (unsigned long long)counter << shift;
        cout << ans << "\n";
    }

    return 0;
}

この解説は gemini-3.5-flash-high によって生成されました。