概要

当選番号のリストと手持ちの宝くじ番号のリストが与えられたとき、当選している宝くじの枚数を数える問題です。

考察

問題の本質

この問題は「2つのリストに共通する要素の個数を数える」という問題に帰着できます。

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

最も単純な方法は、手持ちの宝くじ番号 \(B_j\) それぞれについて、当選番号リスト \(A\) を先頭から順に探索することです。

# 素朴なアプローチ（TLEの危険あり）
count = 0
for b in B:
    for a in A:
        if b == a:
            count += 1
            break

この方法では、\(M\) 枚の宝くじそれぞれに対して、最悪 \(K\) 個の当選番号を確認するため、計算量は \(O(K \times M)\) となります。

\(K, M\) がともに最大 \(10^5\) の場合、\(10^5 \times 10^5 = 10^{10}\) 回の比較が必要になり、制限時間内に終わりません（TLE）。

解決策：集合（set）を使う

Pythonの set（集合）を使うと、ある要素が集合に含まれるかどうかを 平均 \(O(1)\) で判定できます。

当選番号を set に格納しておけば、各宝くじ番号が当選しているかどうかを高速に判定できます。

具体例

当選番号 A = {5, 12, 8}（setとして格納）
手持ち   B = [3, 12, 7, 5]

- 3 は A に含まれる？ → No
- 12 は A に含まれる？ → Yes（カウント+1）
- 7 は A に含まれる？ → No
- 5 は A に含まれる？ → Yes（カウント+1）

答え: 2

アルゴリズム

1. 当選番号 \(K\) 個を読み込み、set として格納する
2. 手持ちの宝くじ番号 \(M\) 個を読み込む
3. 各宝くじ番号について、当選番号の set に含まれているか判定し、含まれていればカウントを増やす
4. カウントを出力する

K, M = map(int, input().split())
A = set(map(int, input().split()))  # 当選番号をsetで保持
B = list(map(int, input().split()))

count = sum(1 for b in B if b in A)  # Aに含まれるbの個数を数える
print(count)

計算量

• 時間計算量: \(O(K + M)\)
  • set の構築に \(O(K)\)
  • \(M\) 個の要素それぞれについて set への所属判定に平均 \(O(1)\)、合計 \(O(M)\)
• 空間計算量: \(O(K + M)\)
  • 当選番号を格納する set に \(O(K)\)
  • 手持ち番号を格納するリストに \(O(M)\)

実装のポイント

• set を使う側を選ぶ: 当選番号 \(A\) を set にし、手持ち番号 \(B\) はリストのままでOKです。探索される側を set にすることで高速化できます。

• ジェネレータ式を使った sum: sum(1 for b in B if b in A) は、条件を満たす要素の個数を数える Pythonic な書き方です。

• 別解: len(set(A) & set(B)) のように集合の積集合を使う方法もあります。ただし、\(B\) に重複がある場合は結果が異なるので注意が必要です（この問題では \(B\) も全て異なるため同じ結果になります）。

  ソースコード

K, M = map(int, input().split())
A = set(map(int, input().split()))
B = list(map(int, input().split()))

count = sum(1 for b in B if b in A)
print(count)

---

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