概要

この問題は、高橋君（総和を最大化したい）と青木君（総和を最小化したい）による、伝達ネットワークの設計と値の書き換えに関するゲームです。

\(N\) が最大でも \(12\) と非常に小さいことに着目し、伝達操作の性質から問題を「集合の分割問題」へと帰着させ、深さ優先探索（DFS）を用いてすべての分割パターンを全探索することで解くことができます。

---

考察

1. 伝達操作の性質（高橋君の行動）

1回の伝達操作では、各人 \(i\) の値が送り先 \(A_i\) へ移動し、同じ送り先に集まった値同士が XOR されます。 \(K\) 回の操作を行うと、初期値 \(V_i\) は \(A\) によって決まる一意な宛先に到達します。

制約より \(K \le 10^{18}\) であり、これは人数 \(N \le 12\) に比べて十分に大きいです。高橋君は送り先 \(A\) を自由に設計できるため、\(N\) 人の初期値を任意のグループ（集合の分割）に分けることができます。 具体的には、同じグループに属する人々の初期値を1つの場所に集め、異なるグループの人々は異なる場所に集めることができます。

このようにしてできた各グループ \(S_1, S_2, \ldots, S_m\) について、グループ内の初期値の XOR 和を \(G_r = \bigoplus_{i \in S_r} V_i\) とすると、最終的に残る値は各グループの XOR 和 \(G_1, G_2, \ldots, G_m\) となります。

2. 青木君の最適戦略

青木君は、高橋君が決めたグループ分け（および各グループの XOR 和 \(G_1, \ldots, G_m\)）を見た上で、ちょうど1人の初期値を任意の非負整数 \(X\) に書き換えることができます。

あるグループ \(S_a\) に属する人の値を書き換えると、そのグループの XOR 和 \(G_a\) を任意の非負整数に書き換えることができます。青木君は最終的な総和を最小化したいので、選んだグループの XOR 和を \(0\) に書き換えるのが最適です。

青木君はどのグループの XOR 和でも \(0\) にできるため、最も XOR 和が大きいグループを \(0\) にするのが最も効果的です。したがって、青木君が最適に行動した後の総和は以下のようになります。

\[ \text{（すべてのグループの XOR 和の総和）} - \text{（XOR 和の最大値）} \]

3. 高橋君の最適戦略

高橋君はこの値を最大化したいと考えます。高橋君は集合 \(\{1, 2, \ldots, N\}\) の分割を自由に選べるため、問題は以下のように言い換えられます。

\(N\) 個の要素をいくつかのグループに分割する。 各グループの XOR 和の総和から、その最大値を引いた値を最大化せよ。

具体例 (\(N=3, V = [3, 5, 6]\))

• 分割案1: \(\{1, 2\}\) と \(\{3\}\) に分割
  • グループ1の XOR 和: \(3 \oplus 5 = 6\)
  • グループ2の XOR 和: \(6\)
  • 青木君の操作後の総和: \((6 + 6) - \max(6, 6) = 6\)
• 分割案2: \(\{1\}\), \(\{2\}\), \(\{3\}\) に分割
  • 各グループの XOR 和: \(3, 5, 6\)
  • 青木君の操作後の総和: \((3 + 5 + 6) - \max(3, 5, 6) = 14 - 6 = 8\)

この場合、高橋君は分割案2を選ぶのが最適となり、答えは \(8\) になります。

---

アルゴリズム

\(N \le 12\) において、集合をいくつかのグループに分割する方法の総数（ベル数 \(B_N\)）は、 \(B_{12} = 4,213,597\) 通りです。これはコンピュータにとっては非常に小さな数であり、すべての分割方法を深さ優先探索（DFS）で全探索することが可能です。

DFS による全探索の手順

1. \(idx\) 番目の人を、すでに存在するグループのいずれかに入れるか、新しいグループを作成してそこに入れます。
2. すべての人（\(idx = N\)）をグループに振り分け終えたら、各グループの XOR 和を計算します。
3. 「XOR 和の総和 - XOR 和の最大値」を計算し、これまでの最大値を更新します。

---

計算量

時間計算量

• \(O(B_N \cdot N)\) \(N = 12\) のとき、ベル数 \(B_{12} \approx 4.2 \times 10^6\) です。DFSの各葉（終端状態）において、グループ数は高々 \(N\) 個であるため、各状態での計算は非常に高速です。実行時間制限（通常2秒）に対して、数ミリ秒〜数十ミリ秒で余裕を持って間に合います。

空間計算量

• \(O(N)\) DFSの再帰の深さは最大で \(N\) であり、グループの XOR 和を保持する配列のサイズも最大で \(N\) です。メモリはほとんど消費しません。

---

実装のポイント

• 重複のない分割の列挙: DFSで新しいグループを作成する際、既存のグループが num_groups 個あるとすると、新しいグループのIDは必ず num_groups とします。これにより、グループの順序だけが異なるような重複した分割（例えば {{1}, {2, 3}} と {{2, 3}, {1}}）を二重に探索してしまうのを防ぐことができます。

• XORの対称性: DFSの行きがけ時に g[i] ^= V[idx] で値をグループに追加し、帰りがけ時に再度 g[i] ^= V[idx] を行うことで、同じ変数を使って効率的に状態を戻す（バックトラックする）ことができます。

  ソースコード

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

using namespace std;

int N;
long long K;
vector<long long> V;
long long ans = 0;
long long g[12];

void dfs(int idx, int num_groups) {
    if (idx == N) {
        long long sum = 0;
        long long mx = 0;
        for (int i = 0; i < num_groups; ++i) {
            sum += g[i];
            if (g[i] > mx) mx = g[i];
        }
        ans = max(ans, sum - mx);
        return;
    }
    for (int i = 0; i < num_groups; ++i) {
        g[i] ^= V[idx];
        dfs(idx + 1, num_groups);
        g[i] ^= V[idx];
    }
    g[num_groups] = V[idx];
    dfs(idx + 1, num_groups + 1);
}

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

---

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