概要

\(N\) 人のグループ全員が、あるアトラクションに乗るためには、そのグループの中で「最も身長が低い人」が制限をクリアしている必要があります。この問題は、グループの最小身長を求め、その値以下の身長制限を持つアトラクションの数を数える問題です。

考察

グループ全員がアトラクション \(i\) に乗るための条件は、すべての \(j\) について \(S_i \leq L_j\) が成り立つことです。

これを素直に判定しようとすると、「各アトラクションについて、全員の身長をチェックする」という処理になり、二重ループが必要になります。 しかし、制約を見ると \(N, M \leq 2 \times 10^5\) であるため、単純な二重ループによる解法（計算量 \(O(N \times M)\)）では実行時間制限に間に合いません。

ここで、条件を整理します。 「全員の身長が \(S_i\) 以上である」ということは、「グループ内での最小身長が \(S_i\) 以上である」と言い換えることができます。 つまり、グループの最小身長を \(L_{min}\) とすると、アトラクション \(i\) に全員が乗れる条件は： $\(S_i \leq L_{min}\)$ となります。

一度 \(L_{min}\) を求めてしまえば、各アトラクションに対して \(1\) 回の比較で済むため、大幅に効率化できます。

アルゴリズム

1. メンバーの身長リスト \(L\) から、最小値 \(L_{min}\) を求めます。
2. アトラクションの身長制限リスト \(S\) を順番に確認します。
3. \(S_i \leq L_{min}\) を満たすアトラクションの個数をカウントします。
4. カウントした結果を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 最小身長の計算に \(O(N)\)、各アトラクションの判定に \(O(M)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 入力された身長と制限をリストに保持するために必要なメモリ量です。

実装のポイント

• 効率的な入力: \(N\) や \(M\) が大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が高速です。

• 最小値の取得: Pythonの組み込み関数 min() を使うことで、リスト内の最小値を \(O(N)\) で簡潔に求めることができます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: グループの人数, M: アトラクションの数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # L: メンバーの身長
    l_list = list(map(int, input_data[2:2+n]))
    # S: アトラクションの身長制限
    s_list = list(map(int, input_data[2+n:2+n+m]))
    
    # グループ全員が乗るためには、グループ内の最小身長が
    # アトラクションの身長制限以上である必要がある
    min_height = min(l_list)
    
    # 身長制限がグループの最小身長以下のものをカウントする
    ans = 0
    for s in s_list:
        if s <= min_height:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。