概要

当選番号の集合と手元の宝くじ番号の集合が与えられるので、両方に含まれる番号（共通部分）の個数を数えます。

考察

重要なのは「ある番号が当選番号に含まれるか？」という判定を高速に行うことです。

素朴に、各 \(B_j\) について当選番号リスト \(A\) を最初から最後まで探す（線形探索）と、 - 1 回の探索が \(O(K)\) - それを \(M\) 回行うので合計 \(O(KM)\)

となり、最大で \(10^5 \times 10^5 = 10^{10}\) 回程度の比較が必要になってしまい、実行時間に間に合いません（TLE の原因）。

そこで、当選番号 \(A\) を 集合（set） にしておくと、要素の存在判定 x in a が平均 \(O(1)\) でできるため、全体を高速化できます。

例： - 当選番号 \(A = \{3, 10, 20\}\) - 手元の番号 \(B = [1, 3, 20, 7]\)

このとき、1 in A は偽、3 in A は真、20 in A は真、7 in A は偽なので、当選は 2 枚です。

アルゴリズム

1. 当選番号 \(A_1 \ldots A_K\) を set に格納する（当選番号集合 a）。
2. 手元の各番号 \(B_j\) について、B_j in a を判定する。
3. 真だった回数を合計して出力する。

Python では次のように数え上げられます： - sum(1 for x in b if x in a)

計算量

• 時間計算量: \(O(K + M)\)（set 構築が \(O(K)\)、各照合が平均 \(O(1)\) を \(M\) 回）
• 空間計算量: \(O(K)\)（当選番号を set に保持）

実装のポイント

• 入力が最大 \(2 \times 10^5\) 個程度あるので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 制約より \(A_i\), \(B_j\) はそれぞれ相異なるため重複処理は不要ですが、今回の解法は重複があっても正しく数えられます（ただし「枚数」を数えるので、重複があればその分カウントされます）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    k, m = data[0], data[1]
    a = set(data[2:2 + k])
    b = data[2 + k:2 + k + m]
    ans = sum(1 for x in b if x in a)
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。