Overview

Find the number of lottery tickets held by Takahashi whose numbers match the winning numbers.

Analysis

This problem simply requires determining whether each of Takahashi’s lottery ticket numbers is included among the winning numbers.

A naive approach would be, for each lottery ticket number \(B_j\), to check all winning numbers \(A_i\) to see if there is a match. However, in the worst case, this method requires \(K \times M\) comparisons. Given the constraints \(K, M \leq 10^5\), this results in up to \(10^{10}\) comparisons, which cannot be processed within the time limit (TLE).

To enable fast lookup of winning numbers, we use a set. Python’s set is internally implemented as a hash table, allowing membership checks (the in operator) to be performed in \(O(1)\) on average.

This allows us to quickly determine whether each lottery ticket number is among the winning numbers, requiring only \(O(M)\) lookups in total.

For example, consider the following input:

3 5
10 20 30
10 25 30 40 20

The winning numbers are {10, 20, 30}. Among Takahashi’s lottery ticket numbers [10, 25, 30, 40, 20], 10, 30, and 20 are winners, so the answer is 3.

Algorithm

1. Convert the list of winning numbers \(A\) into a set to create a fast-searchable collection winning_numbers.
2. For each element in Takahashi’s lottery ticket number list \(B\), check whether it is contained in winning_numbers.
3. If it is contained, increment the count.
4. Output the final count.

Complexity

• Time complexity: \(O(K + M)\)
  (\(O(K)\) for constructing the set, \(O(M)\) for searching each lottery ticket)
• Space complexity: \(O(K)\)
  (storing the winning numbers in the set)

Implementation Notes

• By converting the winning numbers to a set, lookup time is reduced.

• Check each lottery ticket number one by one, using the in operator to determine whether it is a winner.

  Source Code

# 入力の読み込み
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)

This editorial was generated by qwen3-coder-480b.