概要

合宿の各日のおやつ予算全てに対して、どの日でも買えるおやつの商品数を数える問題です。

考察

この問題では、各商品 \(i\) について、すべての日 \(j\) に対して \(R_i \leq S_j\) が成り立つかどうかを判定する必要があります。

素朴な方法として、各商品ごとに全予算と比較する方法（二重ループ）が考えられますが、これは最大で \(N \times M = 10^{12}\) 回の比較が必要になり、明らかに時間制限（TLE）を超えてしまいます。

しかしよく考えると、すべての日で条件を満たす必要があるため、最も厳しい予算（最小の \(S_j\)）だけを見れば十分です。つまり、商品の価格 \(R_i\) が \(\min(S_1, S_2, ..., S_M)\) 以下かどうかを判定すればよいのです。

例えば、予算が [100, 200, 50] の場合、最も厳しいのは 50 円なので、価格が 50 円以下の商品だけが選べます。

このように最小値だけを見ることで、各商品の判定が \(O(1)\) で行えるようになり、全体で \(O(N + M)\) の計算量で解くことができます。

アルゴリズム

1. まず、すべての予算 \(S_1, S_2, ..., S_M\) のうち最小値を求める。
2. 各商品の価格 \(R_i\) について、その値が最小予算以下であるかどうかを判定し、条件を満たすものの個数をカウントする。
3. カウント結果を出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。

• 最小値は組み込み関数 min() で求めることができる。

• 条件を満たす商品の数はループで簡単にカウントできる。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    R = list(map(int, data[2:2+N]))
    S = list(map(int, data[2+N:2+N+M]))
    
    min_budget = min(S)
    count = 0
    for r in R:
        if r <= min_budget:
            count += 1
    print(count)

if __name__ == "__main__":
    main()

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