概要

\(K\) 回の伝達後にできる値は、「人の集合ごとの XOR」に分解して考えられます。
この問題は、最終的に「\(N\) 人をいくつかのグループに分け、各グループの XOR の総和から最大のものを 1 つ引いた値を最大化する問題」に帰着できます。

考察

1. 伝達操作後の値は「グループごとの XOR」になる

送り先を表す関数を \(f(i)=A_i\) とします。

1 回の伝達後、人 \(j\) の値は

\(A_i=j\)

を満たす人 \(i\) の値の XOR になります。

同様に、\(K\) 回後には人 \(j\) の値は

\(f^K(i)=j\)

を満たす人 \(i\) の初期値の XOR になります。

つまり、各人 \(i\) は \(K\) 回後にどこか 1 人のところへ到達し、同じ到達先を持つ人たちが 1 つのグループになります。
最終的な値は、そのグループに属する人たちの初期値の XOR です。

2. 任意のグループ分けを実現できる

実は、\(K \geq 1\) であれば、任意のグループ分けを伝達ネットワークで実現できます。

例えば、あるグループ \(G\) に対して代表者 \(r \in G\) を 1 人決めます。
そして、グループ内の全員が \(r\) に送るようにし、\(r\) 自身は自分自身に送るようにします。

すると 1 回後には全員が \(r\) に集まり、その後も \(r\) に留まり続けます。
したがって、\(K\) の値に関係なく同じグループ分けを実現できます。

よって、この問題では \(K\) は答えに影響しません。

3. 青木君の操作は「グループを 1 つ消す」のと同じ

あるグループ \(G\) の XOR を

\(\bigoplus_{i \in G} V_i\)

とします。

青木君がグループ \(G\) 内の 1 人の値を書き換えると、このグループの XOR は任意の非負整数にできます。
なぜなら、書き換える値をうまく選べば、グループ全体の XOR を好きな値に調整できるからです。

青木君は総和を最小化したいので、そのグループの XOR を \(0\) にします。

つまり、青木君は最終的なグループのうち、XOR が最大のグループを 1 つ選んで \(0\) にします。

したがって、高橋君が作ったグループ分けに対する得点は

\(\sum_{\text{グループ } G} \mathrm{xor}(G) - \max_{\text{グループ } G} \mathrm{xor}(G)\)

になります。

4. 解くべき問題

結局、以下の問題を解けばよいです。

• \(N\) 人をいくつかの空でないグループに分ける
• 各グループの値は、そのグループに含まれる \(V_i\) の XOR
• グループの XOR の総和から、最大の XOR を 1 つ引いた値を最大化する

\(N \leq 12\) なので、集合を bitmask で表して部分集合 DP が使えます。

アルゴリズム

1. 各集合の XOR を前計算する

bitmask mask が表す集合について、

\(\mathrm{xor}[mask] = \bigoplus_{i \in mask} V_i\)

を前計算します。

これは最下位ビットを 1 つ取り除くことで、\(O(2^N)\) で計算できます。

2. 「青木君に消されるグループ」を固定する

青木君に消されるグループを ignored とします。

このグループの XOR を

\(L = \mathrm{xor}[ignored]\)

とします。

このグループが最大値として消されるためには、他のすべてのグループの XOR は \(L\) 以下である必要があります。

残りの人集合を

\(remain = full \setminus ignored\)

とします。

この remain を、各グループの XOR が \(L\) 以下になるように分割し、その XOR の総和を最大化します。

3. 部分集合 DP

固定した ignored に対して、

dp[mask] = mask に含まれる人たちを条件を満たすグループに分割したときの、XOR 総和の最大値

とします。

初期値は

\(dp[0] = 0\)

です。

mask が空でないとき、mask の最下位の 1 ビットを含むグループ sub を 1 つ選びます。

そのとき、

\(dp[mask] = \max(dp[mask \setminus sub] + \mathrm{xor}[sub])\)

です。

ただし、条件として

\(\mathrm{xor}[sub] \leq L\)

でなければなりません。

最下位ビットを必ず含む sub だけを列挙することで、同じ分割を重複して数えることを避けられます。

最後に、

dp[remain]

が、ignored を消された場合の得点になります。

これをすべての非空集合 ignored について試し、最大値を答えとします。

計算量

• 時間計算量: \(O(4^N)\)
• 空間計算量: \(O(3^N)\)

\(N \leq 12\) なので十分高速に動作します。

実装のポイント

• xors[mask] に各集合の XOR を前計算しています。

• sublists[mask] には、mask の最下位ビットを必ず含む部分集合だけを前計算しています。

  • これにより、DP 遷移で同じグループ分けを何度も考えずに済みます。

• ignored は青木君に消されるグループなので、必ず非空集合です。

• K は入力で与えられますが、任意のグループ分けが \(K \geq 1\) で実現できるため、実装上は使いません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    V = list(map(int, input().split()))

    S = 1 << N
    full = S - 1

    xors = [0] * S
    for mask in range(1, S):
        lb = mask & -mask
        idx = lb.bit_length() - 1
        xors[mask] = xors[mask ^ lb] ^ V[idx]

    sublists = [[] for _ in range(S)]
    for mask in range(1, S):
        lb = mask & -mask
        rest = mask ^ lb
        s = rest
        arr = sublists[mask]
        while True:
            arr.append(s | lb)
            if s == 0:
                break
            s = (s - 1) & rest

    dp = [0] * S
    ans = 0

    for ignored in range(1, S):
        limit = xors[ignored]
        remain = full ^ ignored

        for mask in range(1, S):
            if mask & ignored:
                continue

            best = -1
            for sub in sublists[mask]:
                val = xors[sub]
                if val <= limit:
                    prev = dp[mask ^ sub]
                    if prev >= 0:
                        cand = prev + val
                        if cand > best:
                            best = cand
            dp[mask] = best

        if dp[remain] > ans:
            ans = dp[remain]

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。