概要

本問題は、有向グラフ上の値の伝達（XOR和）と、相手による1要素の書き換えを伴うゲームにおいて、最終的な値の総和の最大最小（ミニマックス値）を求める問題です。

一見すると複雑なゲームですが、数理的に紐解くことで、両者が最適に行動したときの最終的な総和は常に 「初期値の総和から、初期値の最大値を引いたもの」、すなわち \(\sum V_i - \max(V)\) になることが示せます。

考察

1. 伝達操作のモデル化

高橋君が選ぶ配列 \(A\) は、各頂点からちょうど1本の有向辺が出るグラフ（Functional Graph）とみなせます。 このグラフにおいて、各人 \(i\) から出発して \(K\) 回遷移した先を \(dest(i, K)\) と表すことにします。

\(K\) 回の伝達操作を行った後、各人 \(q\) が持つ値 \(V'_q\) は、 \(dest(i, K) = q\) となるすべての人 \(i\) の初期値 \(V_i\) の XOR 和になります。 $\(V'_q = \bigoplus_{dest(i, K) = q} V_i\)$

2. 青木君の最適な戦略

青木君は、高橋君が \(A\) を決めた後、誰か1人 \(p\) の初期値を任意の非負整数 \(X\) に書き換えることができます。 初期値 \(V_p\) を \(X\) に書き換えることは、初期状態に \(Y = V_p \oplus X\) を XOR することと同等です。

伝達操作は XOR 演算に対して線形であるため、最終状態においては人 \(dest(p, K)\) の値にのみ \(Y\) が XOR されます。 青木君は \(X\) を自由に選べるため、\(Y\) も任意の非負整数にできます。これは、最終状態において「人 \(dest(p, K)\) の最終的な値を任意の非負整数（特に \(0\)）に書き換えられる」ことを意味します。

青木君は最終的な総和を最小化したいので、最終的な値が最も大きい人 \(q^* = dest(p, K)\) を選び、その値を \(0\) に書き換えます。 したがって、青木君が最適に行動した後の総和は以下のようになります。 $\(\sum_{q=1}^N V'_q - \max_{q} V'_q\)$

3. 高橋君の最適な戦略

高橋君はこの値 \(\sum V'_q - \max V'_q\) を最大化したいです。

ここで、高橋君が \(A_i = i\) （全員が自分自身に送る）とした場合を考えます。 このとき、何回操作しても遷移先は変わらないため \(dest(i, K) = i\) となり、最終的な値は初期値のまま（\(V'_i = V_i\)）です。 この場合、青木君は初期値が最大の人の値を \(0\) にするため、総和は \(\sum V_i - \max(V_i)\) になります。

4. これが常に最大値であることの証明

高橋君がどのような \(A\) を選んでも、総和が \(\sum V_i - \max(V_i)\) を超えられないことを示します。

1. XORの性質より、任意の非負整数について \(a \oplus b \le a + b\) が成り立ちます。
2. 初期値が最大である人を \(i^*\) （\(V_{i^*} = \max V_i\)）とし、その \(K\) 手先の遷移先を \(q^* = dest(i^*, K)\) とします。
3. 青木君が引く最大値は、少なくとも \(V'_{q^*}\) 以上です（\(\max_{q} V'_q \ge V'_{q^*}\)）。

これらを利用して、青木君の操作後の総和を上から評価します。

\[\sum_{q} V'_q - \max_{q} V'_q \le \sum_{q \neq q^*} V'_q\]

ここで、右辺は \(dest(i, K) \neq q^*\) であるような人 \(i\) の初期値の XOR 和の総和です。これも各要素の和で上から抑えられます。

\[\sum_{q \neq q^*} V'_q \le \sum_{dest(i, K) \neq q^*} V_i\]

この右辺は、全体の総和 \(\sum V_i\) から、 \(dest(i, K) = q^*\) となる人 \(i\) の初期値の和を引いたものです。 \(dest(i, K) = q^*\) となる人の中には、先ほど定義した \(i^*\) が必ず含まれているため、その和は少なくとも \(V_{i^*} = \max V_i\) 以上です。

\[\sum_{dest(i, K) \neq q^*} V_i = \sum V_i - \sum_{dest(i, K) = q^*} V_i \le \sum V_i - V_{i^*} = \sum V_i - \max V_i\]

以上より、高橋君がどのような \(A\) を選んでも、最終的な総和は \(\sum V_i - \max V_i\) 以下にしかならないことが証明されました。

高橋君は \(A_i = i\) とすることでこの上限を達成できるため、両者が最適に行動したときの答えは常に \(\sum V_i - \max(V_i)\) となります。

アルゴリズム

1. 与えられた配列 \(V\) の総和 sum(V) を計算する。
2. 配列 \(V\) の最大値 max(V) を計算する。
3. sum(V) - max(V) を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 配列の総和と最大値をそれぞれ1回ずつ走査して求めるため、 \(O(N)\) 時間で動作します。
• 空間計算量: \(O(N)\)
  • 入力された配列 \(V\) を保持するためのメモリのみが必要です。

実装のポイント

• 操作回数 \(K\) は最大で \(10^{18}\) と非常に大きな値ですが、最終的な結果は \(K\) に依存しないため、実装上は \(K\) の値を使用する必要はありません。

• 制約の \(N \le 12\) は非常に小さいですが、この \(O(N)\) の解法であれば \(N \le 10^5\) などのより大きな制約でも高速に正解を求めることができます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    V = [int(x) for x in data[2:2+N]]
    
    ans = sum(V) - max(V)
    print(ans)

if __name__ == '__main__':
    solve()

---

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