概要

グループ全員が乗れるアトラクションの数を求める問題です。各アトラクションには身長制限があり、全員がその制限以上である必要があります。

考察

この問題のポイントは、「グループ全員が乗れるアトラクション」とは、グループの中で最も身長が低い人が乗れるかどうかによって決まるということです。

例えば、グループの身長が \([150, 160, 170]\) cm だったとします。このとき、身長制限が \(160\) cm のアトラクションには全員乗れません（150cmの人が乗れない）。一方で、身長制限が \(150\) cm なら全員乗れます。

したがって、以下の手順で解くことができます： 1. グループの中から最小の身長を求める。 2. 各アトラクションの身長制限がその最小身長以下であれば、そのアトラクションに乗れる。

素朴な方法として「各アトラクションについて、全員が乗れるかを確認する」方法も考えられますが、これは最大で \(N \times M\) 回の比較が必要になり、制約が大きいため時間内に処理しきれません（最大 \(4 \times 10^{10}\) 回）。しかし、上記のように「最小身長」だけを見ればよいことに気づけば、計算量を大幅に削減できます。

アルゴリズム

1. 入力からグループの身長リスト \(L\) とアトラクションの身長制限リスト \(S\) を受け取る。
2. \(L\) の中から最小値（最短身長）を求める。これを \(h_{\min}\) とする。
3. 各アトラクションの身長制限 \(S_i\) に対して、\(S_i \leq h_{\min}\) ならばカウントアップする。
4. カウント結果を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  
  • 最小値を求めるのに \(O(N)\)、アトラクションのチェックに \(O(M)\)。
• 空間計算量: \(O(N + M)\)
  
  • 身長リスト \(L\) と制限リスト \(S\) を保持するのに必要。

実装のポイント

• min(L) で最小値を簡単に求められる。
• 条件 S_i <= min_height で判定を行うことで、全員が乗れるかどうかを効率的に判定できる。

## ソースコード

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

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