概要

高橋君が人をグループに分け、各グループのXOR和を計算した上で、青木君が最も大きいグループのXOR和を0にするゲームにおいて、高橋君が最大化できるスコア（全グループのXOR和の総和 - 最大のXOR和）を求める問題です。

考察

1. 伝達操作の結果によるグループ分け

\(K\)回の伝達操作後、各人 \(i\) の値は \(A^K_i\)（\(A\)を\(K\)回適用した先）に送られます。つまり、操作後に人 \(j\) が持つ値は、「\(K\)ステップで人 \(j\) に到達するすべての人の初期値のXOR」となります。 これにより、人々は「\(K\)ステップ後に同じ行き先に到達する人」の集まりであるいくつかのグループに分割され、各グループの最終的な値はそのグループに含まれる人の初期値のXOR和になります。

2. 任意のグループ分割が可能

\(K \geq 1\) の条件下では、高橋君は伝達ネットワーク \(A\) を適切に設計することで、人を任意のグループに分割することができます。 例えば、各グループの代表者を1人決めて自己ループ（\(A_i = i\)）させ、グループの他のメンバーから代表者へ向かう長さ \(K\) のパスを構成すれば、任意のグループ分割を実現できます。

3. 青木君の最適行動

青木君は1人の初期値を任意の非負整数に書き換えることができます。グループ内の他の人のXOR和を \(Y\) としたとき、選んだ1人の値を \(Y\) に書き換えれば、そのグループ全体のXOR和は \(Y \oplus Y = 0\) にできます。 青木君は総和を最小化したいので、XOR和が最も大きいグループを1つ選んでその値を0にするのが最適です。

4. 高橋君の最適行動と全探索

高橋君は、青木君が最大のグループを0にすることを前提に、グループのXOR和の総和から最大のものを引いた値を最大化するようにグループを分割します。 人数 \(N\) は最大12人であり、12人をグループに分割する方法の総数（ベル数）は \(B_{12} = 4213597\) 程度です。したがって、すべてのグループ分割を全探索しても十分に間に合います。

アルゴリズム

深さ優先探索（DFS）を用いて、全員をグループに分割する全パターンを列挙します。 1. DFSの引数として、現在見ている人のインデックス idx を持ちます。 2. idx 番目の人を「既存のグループのいずれかに追加する」か「新しいグループを作る」のいずれかの分岐を行います。 3. 既存のグループに追加する場合は、そのグループのXOR和を XOR V[idx] で更新し、DFSを抜けた後に元に戻すため再度 XOR V[idx] を行います。 4. 全員の割り当てが完了したら（idx == N）、各グループのXOR和の総和と最大値を求め、総和 - 最大値 がそれまでの最大値を上回れば更新します。

計算量

• 時間計算量: \(O(N \cdot B_N)\) （\(B_N\) はベル数。\(N=12\)のとき約 \(5 \times 10^7\) 回の演算となり、十分高速です）
• 空間計算量: \(O(N)\) （再帰の深さとグループのXOR和の配列用）

実装のポイント

• グループのXOR和を配列で管理する際、配列を毎回コピーすると計算量が増えるため、XOR演算の可逆性（\(A \oplus B \oplus B = A\)）を利用して、同じ変数に ^= 演算をして追加・削除を行うと高速かつ簡潔に実装できます。

• すべての人が1つのグループに属する場合、スコアは 総和 - 最大値 = 0 となります。初期値が0の場合を考慮し、答えの初期値は0に設定します。

  ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

int N;
long long V[12];
long long ans = 0;
long long groups[12];
int num_groups = 0;

void dfs(int idx) {
    if (idx == N) {
        if (num_groups == 0) return;
        long long sum = 0;
        long long mx = 0;
        for (int i = 0; i < num_groups; ++i) {
            sum += groups[i];
            mx = max(mx, groups[i]);
        }
        ans = max(ans, sum - mx);
        return;
    }
    
    // 既存のグループに入れる
    for (int i = 0; i < num_groups; ++i) {
        groups[i] ^= V[idx];
        dfs(idx + 1);
        groups[i] ^= V[idx];
    }
    
    // 新しいグループを作る
    groups[num_groups++] = V[idx];
    dfs(idx + 1);
    num_groups--;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long K;
    if (!(cin >> N >> K)) return 0;
    for (int i = 0; i < N; ++i) {
        cin >> V[i];
    }
    
    dfs(0);
    
    cout << ans << endl;
    return 0;
}

この解説は or-glm5.2-high によって生成されました。