概要

\(N\) 台のサーバーを通じてデータを暗号化・送信するシステムにおいて、特定条件下でサーバーの暗号化キーが無効化される「サンドイッチ検知」ルールを考慮した上で、最終的な出力データを求める問題です。

考察

この問題では、データ \(X\) がサーバーを順に通過し、各サーバーで XOR 演算が適用されます。ただし、あるサーバー \(i\) が「挟まれた異常サーバー」と判定された場合、そのサーバーのキー \(A_i\) の代わりに \(0\) を使うという特殊なルールがあります。

具体的には、連続する3台のサーバー \(i-1, i, i+1\) に対して
- \(A_{i-1} = A_{i+1}\) かつ
- \(A_{i-1} \ne A_i\)

が同時に成り立つとき、サーバー \(i\) のキーは無効化されます。

この条件を愚直に全探索で確認しても、十分高速に動作しますが、制約が \(N \leq 2 \times 10^5\) であるため、入力の読み取りや処理方法に注意が必要です。特にPythonでは、sys.stdin.read を用いて一度に読み込むことで高速化できます。

また、XOR演算は結合的かつ可換的であるため、途中のキーが変わるだけなので、逐次処理が可能です。つまり、各ステップで実際に使用するキー（通常は \(A_i\)、条件を満たす場合は \(0\)）を決定し、現在の結果とXORしていくだけで答えが得られます。

アルゴリズム

1. 入力を高速に読み込み、\(N\), \(X\), \(A_1, A_2, ..., A_N\) を取得します。
2. 結果の初期値を \(X\) とします。
3. 各サーバー \(i = 0\) から \(N-1\) まで以下の処理を行います：
   • サーバー \(i\) が「挟まれた異常サーバー」かどうかを判定します（両隣が存在し、かつ条件を満たすか）。
   • 条件を満たす場合は、キーを \(0\) とし、そうでなければ \(A_i\) を使います。
   • 現在の結果とキーのXORをとります。
4. 最終的な結果を出力します。

計算量

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

実装のポイント

• 入力の受け取りに sys.stdin.read を使い、高速に処理する。
• サンドイッチ条件を判定する際、配列外参照にならないよう \(1 \le i \le N-2\) の範囲で確認する。
• XORはビット演算子 ^ を使用する。

## ソースコード

```python
import sys

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

    # 初期値設定
    result = X

    # 各サーバーの有効なキーを計算しながらXORしていく
    for i in range(N):
        key = A[i]
        # サンドイッチ条件のチェック（端点は該当しない）
        if 1 <= i <= N - 2:
            if A[i - 1] == A[i + 1] and A[i - 1] != A[i]:
                key = 0
        result ^= key

    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。