概要

各日のおやつ予算をすべて満たす商品の数を求める問題です。具体的には、商品の価格がすべての日の予算以下であるような商品の数を数えます。

考察

問題の条件は「商品の価格 \(R_i\) がすべての日の予算 \(S_j\) 以下である」ことです。これは数学的に言い換えると、\(R_i \leq \min(S)\) が成り立つことと等価です。なぜなら、\(R_i\) が最小の予算以下であれば、それより大きい予算の日でも当然 \(R_i \leq S_j\) が成り立つからです。逆に、最小の予算より大きい価格の商品は、最小予算の日で条件を満たせません。したがって、条件を満たす商品は、価格が予算の最小値以下であるものだけです。

アルゴリズム

1. すべての日の予算 \(S\) の最小値 \(\min(S)\) を求める
2. 各商品の価格 \(R_i\) について、\(R_i \leq \min(S)\) であるかをチェックする
3. 条件を満たす商品の数を数えて出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 予算リスト \(S\) の最小値を求めるのに \(O(M)\)
  • 商品リスト \(R\) を走査するのに \(O(N)\)
• 空間計算量: \(O(N + M)\)
  • 入力データを格納するためのメモリ

実装のポイント

• 入力データの読み込みは一度にまとめて行い、効率的に処理します

• 最小値の計算には組み込み関数 min() を使用します（内部で最適化されている）

• 条件チェックは単純なループで行い、条件を満たすものだけをカウントします

  ソースコード

def main():
    import sys
    data = sys.stdin.read().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 price in R:
        if price <= min_budget:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。