概要

招待客の追加（記録）と、特定の招待客が既にリストに含まれているかの確認（問い合わせ）を、大量のクエリに対して高速に処理する問題です。

考察

この問題のポイントは、「データの追加」と「データの検索」をいかに高速に行うかという点にあります。

素朴なアプローチ

例えば、招待客リストを「配列（Pythonのリスト）」で管理することを考えてみましょう。 - 追加: リストの末尾に要素を追加するだけなので \(O(1)\) で済みます。 - 検索: 指定された番号がリスト内にあるかを探すには、リストを先頭から順に見ていく必要があるため、リストの要素数を \(N\) とすると最大で \(O(N)\) の時間がかかります。

今回の問題では操作回数 \(Q\) が最大 \(2 \times 10^5\) です。最悪の場合、検索操作を繰り返すと全体の計算量が \(O(Q^2)\) に達してしまい、実行時間制限（通常 2秒程度）に間に合いません（\(2 \times 10^5\) の 2 乗は \(4 \times 10^{10}\) となり、非常に大きな数になります）。

効率的な解決策

招待客番号 \(X_i\) は最大 \(10^9\) と非常に大きな値であるため、番号をそのまま配列のインデックス（添字）として使うことはできません。 そこで、ハッシュテーブルというデータ構造を利用します。Pythonでは set（集合型）がこれに該当します。

ハッシュテーブルを使用すると、データの追加と検索を平均 \(O(1)\) で行うことができます。これにより、全クエリを \(O(Q)\) の時間で処理することが可能になります。

アルゴリズム

1. 空の集合（set）を用意し、これを guest_list とします。
2. \(Q\) 回の操作を順番に処理します。
   • \(T_i = 1\) のとき: guest_list に \(X_i\) を追加します。
   • \(T_i = 2\) のとき: guest_list に \(X_i\) が含まれているかを確認します。含まれていれば Yes、いなければ No を出力用のリストに格納します。
3. 全ての操作が終わった後、結果をまとめて出力します。

計算量

• 時間計算量: \(O(Q)\)
  • 各操作（追加・検索）は平均 \(O(1)\) で行われます。これを \(Q\) 回繰り返すため、全体の計算量は \(O(Q)\) となります。
• 空間計算量: \(O(Q)\)
  • 最大で \(Q\) 個の招待客番号を集合に保存するため、その分のメモリが必要になります。

実装のポイント

• 入出力の高速化: \(Q\) が \(2 \times 10^5\) と大きいため、Pythonの標準的な input() や print() を繰り返すと入出力がボトルネックになる可能性があります。sys.stdin.read().split() で一括で入力を取得し、結果をリストに溜めて最後に sys.stdout.write() でまとめて出力することで、実行時間を大幅に短縮できます。

• 文字列としての処理: 今回の問題では招待客番号 \(X_i\) に対して計算（足し算など）を行う必要はありません。そのため、数値を int() 型に変換せず、文字列のまま set で管理することで、変換にかかる時間を節約しています。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 操作回数 Q
    Q = int(input_data[0])
    
    # ゲストリストをセット(集合型)で管理 (追加・検索ともに平均O(1))
    guest_list = set()
    
    # 出力を高速化するためにリストに格納して最後にまとめて出力する
    results = []
    
    # 各操作を処理
    # input_data[1], input_data[2] が最初の操作の T_1, X_1
    for i in range(Q):
        t = input_data[1 + 2 * i]
        x = input_data[2 + 2 * i]
        
        if t == '1':
            # 操作1: ゲストリストに追加
            guest_list.add(x)
        else:
            # 操作2: ゲストリストに含まれているか確認
            if x in guest_list:
                results.append("Yes")
            else:
                results.append("No")
    
    # まとめて出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。