概要

高橋君が持っている \(M\) 枚の宝くじの番号の中に、発表された \(K\) 個の当選番号がいくつ含まれているかを数える問題です。

考察

まず、最も単純な方法（全探索）を考えてみます。それぞれの宝くじについて、当選番号のリストを一つずつ確認していく方法です。 この場合、1枚の宝くじにつき最大 \(K\) 回の比較が必要になり、全体では \(O(K \times M)\) の計算量となります。 今回の制約では \(K, M \leq 10^5\) なので、計算回数は最大で \(10^{10}\) 回に達し、一般的な実行時間制限（2秒程度）を大幅に超えてしまいます（TLE: Time Limit Exceeded）。

高速に解くためには、「ある番号が当選番号のリストの中に存在するか」という判定を高速に行う必要があります。

アルゴリズム

「ある要素が集合に含まれているか」を高速に判定するために、ハッシュセット（Pythonでは set 型）を利用します。

1. 当選番号 \(A_1, A_2, \ldots, A_K\) をすべてハッシュセットに格納します。
2. 高橋君の宝くじ \(B_1, B_2, \ldots, B_M\) を一つずつ取り出し、その番号がハッシュセットに含まれているかを確認します。
3. 含まれていれば、一致した枚数としてカウントを 1 増やします。

ハッシュセットを使用すると、要素の挿入や検索を平均 \(O(1)\) で行うことができます。これにより、全探索に比べて劇的に処理が高速化されます。

計算量

• 時間計算量: \(O(K + M)\)
  • 当選番号 \(K\) 個をセットに追加するのに \(O(K)\)、宝くじ \(M\) 枚をそれぞれセットで検索するのに \(O(M)\) かかるため、全体で \(O(K + M)\) となります。
• 空間計算量: \(O(K + M)\)
  • 当選番号をセットに保持するために \(O(K)\)、入力をリストとして保持する場合に \(O(K + M)\) のメモリを使用します。

実装のポイント

• 高速な入出力: 入力の数（\(K + M\)）が最大 \(2 \times 10^5\) と多いため、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行時間を短縮できます。

• データ型の選択: 宝くじの番号は最大 \(10^9\) と大きいですが、一致するかどうかを判定するだけなので、整数型（int）に変換せず文字列型（str）のまま set で管理しても正しく動作します。変換の手間を省くことで、わずかに実行速度が向上します。

  ソースコード

import sys

def solve():
    # Read all input tokens from standard input
    data = sys.stdin.read().split()
    if not data:
        return
    
    # K: Number of winning numbers
    # M: Number of Takahashi's tickets
    K = int(data[0])
    M = int(data[1])
    
    # Store winning numbers in a set for O(1) average time complexity lookups
    # Numbers are treated as strings for efficiency, which is safe for integer comparison
    winning_numbers = set(data[2:2+K])
    
    # Takahashi's ticket numbers
    takahashi_tickets = data[2+K:2+K+M]
    
    # Count how many of Takahashi's tickets match the winning numbers
    match_count = 0
    for ticket in takahashi_tickets:
        if ticket in winning_numbers:
            match_count += 1
            
    # Output the result
    print(match_count)

if __name__ == '__main__':
    solve()

---

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