概要

\(N\) 台のサーバーを順にデータが通過し、各サーバーで暗号化キーとの XOR が行われます。ただし「サンドイッチ検知」条件を満たすサーバーはキーが \(0\) に置き換わります。最終的な出力データを求める問題です。

考察

XOR の基本性質

データ \(X\) がサーバー \(1, 2, \ldots, N\) を順に通過し、各サーバーでキー \(A_i\) との XOR が計算されます。つまり最終結果は：

\[X \oplus A_1 \oplus A_2 \oplus \cdots \oplus A_N\]

となります。XOR は結合法則・交換法則が成り立つため、順番に関係なく全てのキーの XOR を取れば良いのです。

サンドイッチ検知

ただし、連続する 3 台のサーバー \(i, i+1, i+2\) について \(A_i = A_{i+2}\) かつ \(A_i \neq A_{i+1}\) が成り立つとき、サーバー \(i+1\) のキーは \(0\) に置き換えられます。

具体例: \(A = [5, 3, 5]\) の場合、\(A_1 = A_3 = 5\) かつ \(A_1 \neq A_2\) なので、サーバー \(2\) のキーは \(0\) に置き換わります。実効的なキーは \([5, 0, 5]\) となります。

素朴なアプローチで十分か

この問題では \(N \leq 2 \times 10^5\) なので、\(O(N)\) の処理で十分間に合います。サンドイッチ検知の判定も各 \(i\) について定数時間で行えるため、特別なアルゴリズムは不要です。

アルゴリズム

1. 入力を読み取る: \(N\), \(X\), 配列 \(A\) を取得します。
2. 実効キーの決定: 配列 \(A\) のコピー effective を作り、各 \(i\)（\(0 \leq i \leq N-3\)、0-indexed）について以下を確認します：
   • \(A[i] = A[i+2]\) かつ \(A[i] \neq A[i+1]\) ならば、effective[i+1] = 0 とする。
3. XOR の累積計算: \(X\) に対して effective[0], effective[1], ..., effective[N-1] を順に XOR していきます。
4. 結果を出力します。

具体例: - \(N=5, X=10, A=[3, 7, 3, 7, 3]\) の場合 - \(i=0\): \(A[0]=3, A[1]=7, A[2]=3\) → \(3=3\) かつ \(3 \neq 7\) → effective[1] = 0 - \(i=1\): \(A[1]=7, A[2]=3, A[3]=7\) → \(7=7\) かつ \(7 \neq 3\) → effective[2] = 0 - \(i=2\): \(A[2]=3, A[3]=7, A[4]=3\) → \(3=3\) かつ \(3 \neq 7\) → effective[3] = 0 - 実効キー: \([3, 0, 0, 0, 3]\) - 結果: \(10 \oplus 3 \oplus 0 \oplus 0 \oplus 0 \oplus 3 = 10\)

計算量

• 時間計算量: \(O(N)\) — サンドイッチ検知の判定に \(O(N)\)、XOR の累積計算に \(O(N)\)
• 空間計算量: \(O(N)\) — 配列 \(A\) と実効キー配列の保持

実装のポイント

• サンドイッチ検知の判定では、元の配列 \(A\) の値を参照して判定することが重要です。effective 配列を書き換えた後の値で判定してしまうと結果が変わる可能性があるため、判定は必ず元の \(A\) に対して行います。

• \(N < 3\) の場合はサンドイッチ検知が発生しないため、ループが実行されず自然に正しく処理されます。

• XOR の性質として \(a \oplus 0 = a\) が成り立つので、キーを \(0\) に置き換えることは「そのサーバーの暗号化処理を無効化する」ことと等価です。

  ソースコード

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    X = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]
    idx += N

    # Determine which servers are "sandwiched abnormal servers"
    # Server i+1 (0-indexed: i+1) is abnormal if A[i] == A[i+2] and A[i] != A[i+1]
    # for consecutive triple i, i+1, i+2 (0-indexed)
    effective = A[:]
    for i in range(N - 2):
        if A[i] == A[i + 2] and A[i] != A[i + 1]:
            effective[i + 1] = 0

    result = X
    for i in range(N):
        result ^= effective[i]

    print(result)

main()

この解説は claude4.6opus-thinking によって生成されました。