概要

暗号化は「受け取った値に自分のキーを XOR する」を左から順に繰り返す操作なので、最終結果は「\(X\) と実際に使われたキー全体の XOR」で一発で求まります。あとは「サンドイッチ検知」で \(0\) 扱いになるサーバーのキーを打ち消すだけです。

考察

重要な気づき 1：XOR の連鎖はまとめて計算できる

サーバー \(1\) から \(N\) まで通常通りに処理すると、出力は

• サーバー1後：\(X \oplus A_1\)
• サーバー2後：\((X \oplus A_1) \oplus A_2 = X \oplus A_1 \oplus A_2\)
• …
• 最後：\(X \oplus A_1 \oplus A_2 \oplus \cdots \oplus A_N\)

となります。XOR は結合法則・交換法則が成り立つため、逐次シミュレーションしなくても「全部まとめて XOR」すれば同じ結果になります。

重要な気づき 2：「0 を使う」は「そのキーを使わない」と同じ

サンドイッチ検知により、あるサーバー \(j\)（\(2 \le j \le N-1\)）が

• \(A_{j-1} = A_{j+1}\) かつ \(A_{j-1} \ne A_j\)

を満たすとき、サーバー \(j\) は \(A_j\) の代わりに \(0\) を XOR します。

しかし XOR では \(Y \oplus 0 = Y\) なので、これは「本来 \(A_j\) を XOR するはずだったのに、しない」ことと同じです。

どうやって最終結果を作るか

まず通常通りの総 XOR を

• \(\text{total} = A_1 \oplus A_2 \oplus \cdots \oplus A_N\)

とします。ここから、0 扱いになったサーバー \(j\) については \(A_j\) を「使わない」ので、\(\text{total}\) から \(A_j\) を除去する必要があります。

XOR の世界では「除去」はもう一度 XOR することと同じです（\(A \oplus A = 0\)）：

• \(\text{total} \oplus A_j\) とすると、\(\text{total}\) 内の \(A_j\) が打ち消される

よって、0 扱いになるサーバーのキーを全部 XOR した

• \(\text{abnormal} = \bigoplus(\text{0扱いの } A_j)\)

を用意すると、答えは

• \(\text{ans} = X \oplus \text{total} \oplus \text{abnormal}\)

になります。

（例） \(A = [5, 7, 5]\) のとき、真ん中は \(A_1=A_3\) かつ \(A_2 \ne A_1\) なので 0 扱い。 - 通常：\(X \oplus 5 \oplus 7 \oplus 5\) - 実際：\(X \oplus 5 \oplus 0 \oplus 5 = X\) 上の式でも \(\text{total}=5\oplus7\oplus5=7\)、\(\text{abnormal}=7\) なので \(X \oplus 7 \oplus 7 = X\) となり一致します。

素朴なアプローチが危ない点

逐次シミュレーション自体は \(O(N)\) で可能ですが、「0 扱いの判定」を毎回周辺を探したり、判定対象を何度も調べ直すような実装にすると、最悪で \(O(N^2)\) のような無駄が出ます。
本問では判定は各 \(j\) について一度（\(A_{j-1},A_j,A_{j+1}\) を見るだけ）で十分なので、全体を 1 回なぞるだけで解けます。

アルゴリズム

1. 配列 \(A\) の全要素の XOR を取って total_xor を作る。
2. \(i=1\) から \(N-2\)（0-index なら i=0..N-3）について三つ組 \((A_i, A_{i+1}, A_{i+2})\) を見て、
   • \(A_i = A_{i+2}\) かつ \(A_i \ne A_{i+1}\) なら、abnormal_xor ^= A[i+1]
3. 答えを X ^ total_xor ^ abnormal_xor として出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列 \(A\) を除く追加領域）

実装のポイント

• 0-index で実装する場合、サンドイッチ判定は i=0..N-3 の範囲で A[i], A[i+1], A[i+2] を見るのが安全です。

• XOR は ^ 演算子（Python）で計算できます。

• \(N\) が最大 \(2\times 10^5\) なので、Python では sys.stdin.buffer.read() でまとめて高速に読むと安定します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, X = data[0], data[1]
    A = data[2:2 + N]

    total_xor = 0
    for v in A:
        total_xor ^= v

    abnormal_xor = 0
    for i in range(N - 2):
        if A[i] == A[i + 2] and A[i] != A[i + 1]:
            abnormal_xor ^= A[i + 1]

    print(X ^ total_xor ^ abnormal_xor)

if __name__ == "__main__":
    main()

---

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