概要

高橋君が持っている宝くじの番号のうち、当選番号と一致するものの個数を求めます。

考察

この問題は、高橋君が持っている各宝くじの番号が、当選番号の中に含まれているかどうかを判定するだけです。

素朴な方法としては、各宝くじの番号 \(B_j\) に対して、すべての当選番号 \(A_i\) を見て一致するものがあるかを調べる方法があります。しかし、この方法では最悪の場合、\(K \times M\) 回の比較が必要になり、制約が \(K, M \leq 10^5\) なので、最大で \(10^{10}\) 回の比較となり、時間内に処理しきれません（TLE）。

そこで、当選番号を高速に検索できるようにするために、集合（set） を使います。Python の set は内部的にハッシュテーブルで実装されており、要素の存在確認（in 演算子）が平均的に \(O(1)\) で行えます。

これにより、各宝くじの番号について、当選番号に含まれるかどうかを高速に判定でき、全体で \(O(M)\) 回の検索で済みます。

たとえば、以下のような入力を考えましょう：

3 5
10 20 30
10 25 30 40 20

当選番号は {10, 20, 30} です。高橋君の宝くじ番号 [10, 25, 30, 40, 20] のうち、10, 30, 20 が当選しているので、答えは 3 です。

アルゴリズム

1. 当選番号のリスト \(A\) を set に変換し、高速検索可能な集合 winning_numbers を作る。
2. 高橋君の宝くじ番号のリスト \(B\) の各要素について、それが winning_numbers に含まれるかをチェックする。
3. 含まれていればカウントを増やす。
4. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(K + M)\)
  （set の構築に \(O(K)\)、各宝くじの検索に \(O(M)\)）
• 空間計算量: \(O(K)\)
  （set に当選番号を格納）

実装のポイント

• 当選番号を set に変換することで、検索時間を削減する。
• 各宝くじの番号を1つずつ確認し、in 演算子で当選有無を判定する。

## ソースコード

```python
# 入力の読み込み
K, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 当選番号をセットに変換して高速検索可能にする
winning_numbers = set(A)

# 高橋君の宝くじ番号のうち、当選しているものをカウント
count = 0
for number in B:
    if number in winning_numbers:
        count += 1

# 結果の出力
print(count)

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