概要

招待客の到着を記録し、特定の招待客が既に到着しているかを高速に判定する問題です。集合（set）を使うことで効率的に解くことができます。

考察

問題の整理

この問題では2種類の操作を処理する必要があります： 1. 追加操作（T=1）: 招待客番号をゲストリストに追加 2. 検索操作（T=2）: 招待客番号がゲストリストに存在するか確認

素朴なアプローチの問題点

もしゲストリストを通常のリスト（配列）で管理すると： - 追加操作: \(O(1)\) で可能（末尾に追加） - 検索操作: \(O(N)\) かかる（リスト全体を走査）

最悪の場合、\(Q\) 回の操作それぞれで \(O(Q)\) の検索が発生し、全体で \(O(Q^2)\) となります。\(Q = 2 \times 10^5\) のとき、これは約 \(4 \times 10^{10}\) 回の操作となり、TLE（時間超過） になってしまいます。

解決策

集合（set） を使えば、追加も検索も平均 \(O(1)\) で処理できます。

集合は内部でハッシュテーブルを使用しており、要素の有無を高速に判定できるデータ構造です。

アルゴリズム

1. 空の集合 guest_set を用意する
2. 各操作を順番に処理する：
   • T=1 の場合: guest_set に招待客番号 \(X\) を追加
   • T=2 の場合: \(X\) が guest_set に含まれているかを確認し、結果を記録
3. すべての検索結果をまとめて出力する

具体例

入力例：

5
1 100
1 200
2 100
2 300
1 300

操作	T	X	処理内容	guest_set の状態	出力
1	1	100	100を追加	{100}	-
2	1	200	200を追加	{100, 200}	-
3	2	100	100が存在するか？	{100, 200}	Yes
4	2	300	300が存在するか？	{100, 200}	No
5	1	300	300を追加	{100, 200, 300}	-

計算量

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

  • 集合への追加: 平均 \(O(1)\)
  • 集合での検索: 平均 \(O(1)\)
  • \(Q\) 回の操作を処理するので、全体で \(O(Q)\)

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

  • 最大で \(Q\) 個の招待客番号を集合に保存する可能性がある

実装のポイント

1. 高速な入力: sys.stdin.readline を使用することで、大量の入力を高速に読み込めます。

2. 出力のまとめ処理: 検索結果を毎回 print するのではなく、リストに溜めておいて最後に '\n'.join() でまとめて出力すると高速です。

3. Pythonの set: Pythonの set は以下の操作が平均 \(O(1)\) で行えます：

   • set.add(x): 要素の追加
   • x in set: 要素の存在確認

4. 招待客番号の範囲: \(X\) は最大 \(10^9\) と大きいですが、集合を使えばメモリ効率よく管理できます（実際に登場する番号のみを保存するため）。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    Q = int(input())
    guest_set = set()
    results = []
    
    for _ in range(Q):
        T, X = map(int, input().split())
        if T == 1:
            guest_set.add(X)
        else:  # T == 2
            if X in guest_set:
                results.append("Yes")
            else:
                results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

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