Overview

This is a problem of finding the number of attractions that everyone in the group can ride. Each attraction has a height restriction, and everyone in the group must meet or exceed that restriction.

Analysis

The key insight of this problem is that whether “everyone in the group can ride an attraction” is determined by whether the shortest person in the group can ride it.

For example, suppose the group’s heights are \([150, 160, 170]\) cm. In this case, not everyone can ride an attraction with a height restriction of \(160\) cm (the person who is 150 cm cannot ride). On the other hand, if the height restriction is \(150\) cm, then everyone can ride.

Therefore, the problem can be solved with the following steps: 1. Find the minimum height in the group. 2. If an attraction’s height restriction is less than or equal to that minimum height, then everyone can ride that attraction.

A naive approach of “checking whether everyone can ride for each attraction” is also conceivable, but this requires up to \(N \times M\) comparisons, which cannot be processed within the time limit given the large constraints (up to \(4 \times 10^{10}\) comparisons). However, by realizing that we only need to look at the “minimum height,” we can significantly reduce the computational complexity.

Algorithm

1. Read the group’s height list \(L\) and the attraction height restriction list \(S\) from input.
2. Find the minimum value (shortest height) in \(L\). Call this \(h_{\min}\).
3. For each attraction’s height restriction \(S_i\), increment the count if \(S_i \leq h_{\min}\).
4. Output the count.

Complexity

• Time complexity: \(O(N + M)\)
  
  • \(O(N)\) to find the minimum value, and \(O(M)\) to check the attractions.
• Space complexity: \(O(N + M)\)
  
  • Required to store the height list \(L\) and the restriction list \(S\).

Implementation Notes

• The minimum value can be easily obtained using min(L).

• By using the condition S_i <= min_height, we can efficiently determine whether everyone can ride.

  Source Code

# 入力の読み込み
N, M = map(int, input().split())
L = list(map(int, input().split()))
S = list(map(int, input().split()))

# グループの最小身長を求める
min_height = min(L)

# 最小身長以上であるアトラクションの数をカウント
count = 0
for s in S:
    if s <= min_height:
        count += 1

# 結果の出力
print(count)

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