概要

各日の予算 \(S_j\) をすべて満たせる（毎日買える）商品とは、価格 \(R_i\) が「予算の最小値以下」である商品です。その個数を数えます。

考察

条件は「すべての日 \(j\) で \(R_i \le S_j\)」です。これは不等式の性質から

• \(R_i \le S_1\)
• \(R_i \le S_2\)
• \(\dots\)
• \(R_i \le S_M\)

を同時に満たす必要があります。

ここで重要な気づきは、すべての \(S_j\) のうち最小の予算を \(B = \min(S_1,\dots,S_M)\) とすると、

• \(R_i \le S_j\) が全日で成り立つ
  \(\Longleftrightarrow\) 特に一番小さい日にも買える（\(R_i \le B\)）

つまり判定は \(R_i \le \min S\) だけで十分です。

素朴に各商品 \(i\) について全日 \(j\) をチェックすると \(O(NM)\) となり、最大で \(10^6 \times 10^6 = 10^{12}\) 回比較になって間に合いません。
そこで、先に \(\min S\) を一度だけ求め、あとは各商品の価格と比較して数えるだけにします。

例： - 予算 \(S = [300, 250, 400]\) なら \(\min S = 250\) - 価格 \(R = [200, 260, 250]\) のうち、\(250\) 以下は \(200, 250\) の2つ
\(\Rightarrow\) 答えは 2

アルゴリズム

1. 入力で与えられる \(M\) 個の予算 \(S_j\) を読みながら、最小値 \(B=\min S\) を求める。
2. \(N\) 個の価格 \(R_i\) について、\(R_i \le B\) を満たす個数を数える。
3. その個数を出力する。

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(N)\)（価格を保持するため。保持せずに読みながら数えれば \(O(1)\) も可能）

実装のポイント

• \(N, M \le 10^6\) と入力が非常に大きいので、sys.stdin.buffer.read() でまとめて読み、手動で整数をパースして高速化しています。

• 予算は最小値だけ必要なので、配列に保存せず読みながら min_budget を更新しています。

• 価格は array('I')（C風の整数配列）で保持し、Pythonの通常の list よりメモリ効率を良くしています。

  ソースコード

import sys
from array import array

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = next_int()
    M = next_int()

    prices = array('I')
    prices_extend = prices.append
    for _ in range(N):
        prices_extend(next_int())

    min_budget = 10**9 + 1
    for _ in range(M):
        s = next_int()
        if s < min_budget:
            min_budget = s

    cnt = 0
    for r in prices:
        if r <= min_budget:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

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