概要

グループ全員が乗れるには「一番身長が低い人でも条件を満たす」必要があるので、最小身長を基準にして乗れるアトラクション数を数えます。

考察

メンバー \(j\) がアトラクション \(i\) に乗れる条件は \(S_i \le L_j\) です。
「全員が乗れる」ためには、全員についてこの不等式が成り立つ必要があります。

ここで重要な観察は次の通りです：

• 全員が乗れる \(\Leftrightarrow\) 一番身長が低い人（最小身長）でも乗れる
  なぜなら、最小身長を \(L_{\min}=\min(L_1,\dots,L_N)\) とすると、
  • \(S_i \le L_{\min}\) なら、他のメンバーは \(L_j \ge L_{\min}\) なので全員乗れる
  • \(S_i > L_{\min}\) なら、最小身長の人が乗れないので全員では乗れない

したがって、答えは「\(S_i \le L_{\min}\) を満たすアトラクションの個数」です。

素朴に「各アトラクションごとに全員をチェック」すると、最悪で \(M \times N \le 4 \times 10^{10}\) 回比較が必要になり、制約下では到底間に合いません（TLE）。
最小身長だけ見ればよいと分かれば、比較回数は \(M\) 回に減ります。

例： - 身長 \(L=[150, 170, 160]\) なら \(L_{\min}=150\) - 制限 \(S=[140, 150, 151, 130]\) のうち \(150\) 以下は \(140,150,130\) の3つ
よって答えは 3

アルゴリズム

1. メンバーの身長配列 \(L\) の最小値 \(L_{\min}\) を求める。
2. アトラクションの制限配列 \(S\) について、\(S_i \le L_{\min}\) を満たす個数を数える。
3. その個数を出力する。

計算量

• 時間計算量: \(O(N+M)\)（最小値計算に \(O(N)\)、カウントに \(O(M)\)）
• 空間計算量: \(O(1)\)（入力配列を除けば追加メモリは定数）

実装のポイント

• 「全員が乗れる条件」は最小身長だけで判定できる点が核心です。

• 入力が最大 \(2 \times 10^5\) と大きいので、Python では sys.stdin.buffer.read() でまとめて読むと高速です。

• カウントは sum(1 for x in S if x <= min_height) のように簡潔に書けます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    L = data[2:2+N]
    S = data[2+N:2+N+M]
    min_height = min(L)
    ans = sum(1 for x in S if x <= min_height)
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。