概要

\(N\) 種類の商品の中から、すべての日のおやつ予算の範囲内で購入できる商品の数を求める問題です。

考察

「すべての日において商品の価格 \(R_i\) が予算 \(S_j\) 以下である」という条件の扱い方がポイントです。

素朴に考えると、ある商品 \(i\) について、\(M\) 日間すべての日で \(R_i \leq S_j\) が成り立つかをループで確認したくなります。しかし、この方法では \(1\) つの商品を判定するのに \(M\) 回の確認が必要となり、全体で \(N \times M\) 回の計算が発生します。制約は \(N, M \leq 10^6\) なので計算回数が最大 \(10^{12}\) 回に達し、TLE（実行時間制限超過）となってしまいます。

ここで、「すべての予算 \(S_j\) 以下の価格」という条件は、「予算 \(S_j\) の中の最小値以下の価格」と言い換えることができる点に気づくのが重要です。 例えば、予算が \(300\) 円、\(200\) 円、\(400\) 円の日がある場合、すべての日で買える商品の価格は、一番厳しい予算である \(200\) 円（最小値）以下でなければなりません。 したがって、先に予算 \(S_j\) の最小値を求めておけば、各商品について \(1\) 回の比較で条件を満たすか判定できるようになります。

アルゴリズム

1. 毎日のおやつ予算 \(S_1, S_2, \ldots, S_M\) の中から最小値を求め、これを min_S とします。
2. 条件を満たす商品の数を数えるカウンター ans を \(0\) で初期化します。
3. 各商品の価格 \(R_1, R_2, \ldots, R_N\) について、順番に min_S と比較します。
4. \(R_i \leq\) min_S であれば、その商品はすべての日で購入可能なので、ans に \(1\) を加算します。
5. すべての商品を確認し終えたら、ans を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 予算の最小値を求めるのに \(O(M)\)、各商品の価格の判定に \(O(N)\) かかるため、全体の計算量は \(O(N + M)\) となります。
• 空間計算量: \(O(N + M)\)
  • 入力データをすべて配列（リスト）としてメモリに保持するため、入力サイズに比例した空間が必要です。

実装のポイント

• 高速な入出力: \(N\) と \(M\) が最大 \(10^6\) と非常に大きいため、Pythonの標準的な input() を使って \(1\) 行ずつ読み込むと、入力処理だけで実行時間制限に引っかかる可能性があります。正解コードのように sys.stdin.read().split() を用いて入力を一括で読み込み、リスト化する手法が効果的です。

• スライスの活用: 読み込んだデータは \(1\) つの平坦なリスト data になるため、商品の価格部分は data[2 : 2+N]、予算部分は data[2+N : ] とスライスを使って簡単に切り出すことができます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    
    N = data[0]
    
    min_S = min(data[2+N:])
    
    ans = 0
    for r in data[2:2+N]:
        if r <= min_S:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。