概要

カードを積み上げながら XOR 値を管理し、過去に同じ XOR 値が現れた最新のタイミングを求める問題です。

考察

この問題では「山」がスタック構造になっており、カードの追加・削除が行われます。確認操作ではその時点での山全体の XOR 値を求めますが、毎回全カードに対して XOR を計算していたら非効率です。

重要な気づきは、「XOR は可逆的な演算である」ということです。つまり、ある値 \( x \) を XOR してから再度 \( x \) を XOR すると元に戻る性質があります： $\( a \oplus x \oplus x = a \)$

この性質を利用すると、新しいカードを追加するときには現在の XOR 値にそのカードの値を XOR すればよく、カードを取り除くときも同様にそのカードの値をもう一度 XOR することで更新できます。

さらに、確認操作で求めた XOR 値が以前にも出てきたかどうかを高速に判定するために、連想配列（Python なら dict）を使って「XOR 値 → 最後に見た確認操作の番号」を記録しておけば良いです。

素朴な方法（毎回スタックの中身全部で XOR を計算）だと時間計算量が \( O(N^2) \) になってしまい、制約 \( N \leq 2 \times 10^5 \) では間に合いません。

アルゴリズム

1. スタック stack で山の状態を管理。
2. 変数 xor_val で現在の山全体の XOR 値を保持。
3. 辞書 last_index で「XOR 値 → 直近の確認操作の番号」を記録。
4. 各操作を処理：
   • PUT c:
     • \( c \) をスタックに追加。
     • xor_val ^= c で XOR 値を更新。
   • REMOVE:
     • スタックのトップ要素を取り出す。
     • それを再び XOR して xor_val を戻す。
   • LOOK:
     • 現在の xor_val を記録。
     • それが過去に登場していたらその番号を答え、なければ \(-1\)。
     • 辞書を更新して今回の番号を記録。

計算量

• 時間計算量: \( O(N) \)
  • 各操作が定数時間で処理でき、確認操作での検索もハッシュテーブルによる \( O(1) \)。
• 空間計算量: \( O(N) \)
  • スタックとハッシュテーブルのサイズは最大で \( N \)。

実装のポイント

• XOR の可逆性をうまく使って全体の値を効率的に管理する。

• 過去の確認結果を辞書で持っておくことで、一致する値の検索を高速化。

• 入力を高速に読み込むために sys.stdin.read() を使用している。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    
    stack = []  # 山の状態（スタック）
    xor_val = 0  # 現在のXOR値
    look_values = []  # これまでの確認操作でのXOR値を記録
    result = []   # 結果を格納
    
    index = 1
    look_count = 0
    
    # XOR値から直近のインデックスを取得するための辞書
    last_index = dict()
    
    for _ in range(N):
        operation = data[index]
        if operation == "PUT":
            c = int(data[index+1])
            stack.append(c)
            xor_val ^= c
            index += 2
        elif operation == "REMOVE":
            removed = stack.pop()
            xor_val ^= removed
            index += 1
        else:  # LOOK
            look_count += 1
            look_values.append(xor_val)
            
            if xor_val in last_index:
                result.append(last_index[xor_val])
            else:
                result.append(-1)
                
            last_index[xor_val] = look_count
            index += 1
            
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

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