概要

各商品の不良率と製造数の積（リスクスコア）が与えられた値 \(K\) 以上である商品の数を数える問題。

考察

各商品について、不良率 \(A_i\) と製造数 \(B_i\) の積 \(A_i \times B_i\) を計算し、それが \(K\) 以上かどうかを判定すれば良いです。

素朴な方法として、すべての商品に対してこの積を実際に計算して比較する方法がありますが、制約を見ると \(A_i \leq 100\), \(B_i \leq 10^9\) であり、積は最大で \(10^{11}\) 程度になります。これは long long 型（64ビット整数）で扱える範囲なので問題ありません。

また、\(N\) は最大で \(2 \times 10^5\) なので、各商品について定数時間の処理を行うとしても全体で \(O(N)\) となり、十分高速です。

したがって、特に工夫なしに全探索を行っても間に合います。

アルゴリズム

1. 入力から \(N\) と \(K\) を受け取る。
2. 各商品について以下を繰り返す：
   • 不良率 \(A_i\) と製造数 \(B_i\) を入力。
   • リスクスコア \(A_i \times B_i\) を計算。
   • その値が \(K\) 以上であればカウントアップ。
3. カウント結果を出力。

計算量

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

実装のポイント

• 積 \(A_i \times B_i\) は最大で \(10^{11}\) 程度になるので、Pythonのように任意精度整数を持つ言語を使用するか、C++などの場合は long long 型を使う必要があります。
• 入力を効率よく処理するために、不要なリスト保存は避け、必要な情報だけを読み込みながら処理するのが望ましいです。

ソースコード

N, K = map(int, input().split())
count = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A * B >= K:
        count += 1
print(count)

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