概要

\(N\) 種類の商品の中から、合宿のすべての日の予算以下となる商品がいくつあるかを求める問題です。

考察

重要な気づき

「すべての日 \(j\) について \(R_i \leq S_j\)」という条件を考えます。商品 \(i\) の価格 \(R_i\) がすべての日の予算以下であるためには、最も予算が厳しい日（予算が最小の日）でも予算以下であれば十分です。

具体例で考えてみましょう。合宿が3日間で予算が \(S = [500, 300, 400]\) の場合： - 予算の最小値は \(300\) 円 - 価格が \(300\) 円以下の商品なら、\(300\) 円の日も \(400\) 円の日も \(500\) 円の日もすべてクリアできる - 逆に価格が \(301\) 円以上の商品は、\(300\) 円の日に予算オーバーになる

つまり、条件「すべての \(j\) で \(R_i \leq S_j\)」は、「\(R_i \leq \min(S_1, S_2, \ldots, S_M)\)」と同値です。

素朴なアプローチの問題点

商品ごとにすべての日の予算と比較する方法だと、\(O(N \times M)\) の計算量になります。\(N, M\) が最大 \(10^6\) なので、最悪 \(10^{12}\) 回の比較が必要となり、制限時間に間に合いません（TLE）。

解決策

予算の最小値 \(\min(S)\) を先に求めておけば、各商品について1回の比較だけで判定できます。

アルゴリズム

1. 予算の配列 \(S\) の最小値 \(\text{min\_s}\) を求める
2. 各商品の価格 \(R_i\) について、\(R_i \leq \text{min\_s}\) かどうかを判定する
3. 条件を満たす商品の個数を数えて出力する

min_s = min(S)
答え = (R_i <= min_s を満たす i の個数)

計算量

• 時間計算量: \(O(N + M)\)
  • \(\min(S)\) の計算に \(O(M)\)
  • 各商品の判定に \(O(N)\)
• 空間計算量: \(O(N + M)\)
  • 配列 \(R\) と \(S\) の保持に必要

実装のポイント

• min(S) をあらかじめ1回だけ計算し、変数に保存しておくことが重要です。ループの中で毎回 min(S) を呼ぶと \(O(N \times M)\) になってしまいます。

• Python では sum(1 for r in R if r <= min_s) のようにジェネレータ式を使うと、条件を満たす要素の個数を簡潔にカウントできます。

  ソースコード

N, M = map(int, input().split())
R = list(map(int, input().split()))
S = list(map(int, input().split()))
min_s = min(S)
print(sum(1 for r in R if r <= min_s))

---

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