概要

この問題では、招待客の到着を記録し、指定された招待客がすでに到着しているかを効率的に判定する必要があります。

考察

この問題の核心は、「ある要素が集合に含まれているか？」を高速に判定できるデータ構造を選ぶことです。

素朴な方法として、リストや配列を使ってゲストを管理することを考えますが、これにはいくつかの問題があります：

• ゲストの番号が最大 \(10^9\) まであるため、配列を確保するのは現実的ではありません（メモリ制限超過）。
• リストを使って到着者を記録し、確認のたびに線形探索を行うと、最悪ケースで \(O(Q^2)\) の計算時間となり、間に合いません（時間制限超過）。

そこで登場するのが set（集合）型 です。Python の set 型は、要素の挿入・削除・検索を平均 \(O(1)\) で行うことができ、非常に効率的です。今回は、ゲストの到着情報を set に保存することで、高速に処理できます。

アルゴリズム

1. guest_set という空のセットを用意する。
2. 各操作について以下のように処理する：
   • \(T_i = 1\) のとき：guest_set に \(X_i\) を追加する。
   • \(T_i = 2\) のとき：\(X_i\) が guest_set に含まれるかを判定し、結果を記録する。
3. 最後に、すべての結果を改行区切りで出力する。

このアルゴリズムにより、各操作を高速に行うことができます。

計算量

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

各操作が平均 \(O(1)\) で処理されるため、全体で \(O(Q)\) 時間で完了します。また、最大 \(Q\) 個の要素を set に格納するので、空間も \(O(Q)\) です。

実装のポイント

• set を使うことで高速な存在判定が可能になります。

• 入力を一度に読み込み、分割して処理することで入力待ちによる遅延を防ぎます（高速化テクニック）。

• 結果は一旦リストに保存しておき、最後にまとめて出力すると効率的です。

  ソースコード

import sys
input = sys.stdin.read

guest_set = set()
result = []

data = input().split()
Q = int(data[0])
queries = [(int(data[i*2+1]), int(data[i*2+2])) for i in range(Q)]

for T, X in queries:
    if T == 1:
        guest_set.add(X)
    else:
        if X in guest_set:
            result.append("Yes")
        else:
            result.append("No")

print("\n".join(result))

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