概要

グループ全員が乗れるアトラクションの数を求める問題です。全員が乗れる条件は、グループで最も身長が低い人でも身長制限をクリアできることです。

考察

重要な気づき

グループ全員がアトラクションに乗れるためには、全員が身長制限を満たす必要があります。

ここで重要な観察があります： - もしグループで一番身長が低い人が身長制限をクリアできれば、他の全員も必ずクリアできる - 逆に、一番身長が低い人がクリアできなければ、全員では乗れない

つまり、グループの最小身長 \(\geq\) アトラクションの身長制限 であれば、そのアトラクションに全員で乗れます。

具体例で確認

例えば、グループの身長が \([150, 160, 140]\) cm の場合： - 最小身長は \(140\) cm - 身長制限が \(130\) cm のアトラクション → \(130 \leq 140\) なので全員乗れる ✓ - 身長制限が \(145\) cm のアトラクション → \(145 > 140\) なので全員では乗れない ✗

素朴なアプローチとの比較

素朴に考えると、各アトラクションについて全メンバーをチェックする方法があります： - 各アトラクション \(i\) について、全メンバー \(j\) が \(S_i \leq L_j\) を満たすか確認 - これは \(O(N \times M)\) かかり、最悪 \(4 \times 10^{10}\) 回の比較が必要でTLEの恐れがあります

しかし、最小身長だけを見ればよいと気づけば、\(O(N + M)\) で解けます。

アルゴリズム

1. グループメンバーの身長リスト \(L\) から最小値 \(\min(L)\) を求める
2. 各アトラクションの身長制限 \(S_i\) について、\(S_i \leq \min(L)\) を満たすものを数える
3. その個数を出力する

N, M = map(int, input().split())
L = list(map(int, input().split()))
S = list(map(int, input().split()))

min_height = min(L)  # グループの最小身長を求める
count = sum(1 for s in S if s <= min_height)  # 条件を満たすアトラクションを数える
print(count)

計算量

• 時間計算量: \(O(N + M)\)
  • \(\min(L)\) の計算に \(O(N)\)
  • 各アトラクションの判定に \(O(M)\)
• 空間計算量: \(O(N + M)\)
  • 身長リスト \(L\) に \(O(N)\)
  • 身長制限リスト \(S\) に \(O(M)\)

実装のポイント

• Pythonの min() 関数でリストの最小値を簡単に取得できます

• sum(1 for s in S if s <= min_height) はジェネレータ式を使った条件を満たす要素のカウント方法です。len([s for s in S if s <= min_height]) と同じ結果ですが、メモリ効率が良いです

• 制約が \(N, M \leq 2 \times 10^5\) と大きいため、\(O(N \times M)\) のアルゴリズムは避けるべきです

  ソースコード

N, M = map(int, input().split())
L = list(map(int, input().split()))
S = list(map(int, input().split()))

min_height = min(L)
count = sum(1 for s in S if s <= min_height)
print(count)

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