概要

\(N\) 個の商品それぞれについて、不良率 \(A_i\) と製造数 \(B_i\) の積（リスクスコア）を計算し、その値が基準値 \(K\) 以上であるものの個数を求める問題です。

考察

この問題の核心は、各商品に対して「\(A_i \times B_i \geq K\) かどうか」を判定し、条件を満たすものを数え上げるというシンプルなものです。

1. 計算の正確性

リスクスコアの最大値は、不良率の最大値 \(100\) と製造数の最大値 \(10^9\) を掛け合わせた \(100 \times 10^9 = 10^{11}\) となります。一方、基準値 \(K\) は最大で \(10^{18}\) と非常に大きな値になります。 Pythonでは整数の大きさに制限がない（多倍長整数を自動で扱う）ため、これらの大きな数値の計算や比較も、オーバーフローを気にすることなく正確に行うことができます。

2. 実行時間

商品の数 \(N\) は最大で \(2 \times 10^5\) です。各商品に対して行う操作は「掛け算」と「比較」がそれぞれ1回ずつなので、全体で \(2 \times 10^5\) 回程度の計算量になります。これは一般的なプログラミング言語で 1 秒間に処理できる計算量（約 \(10^8\) 回）に対して十分に余裕があるため、各商品を順番にチェックする \(O(N)\) のアルゴリズムで制限時間内に解くことができます。

アルゴリズム

以下の手順で解を求めます。

1. 入力から商品の数 \(N\) と基準値 \(K\) を受け取る。
2. 条件を満たす商品の数を管理する変数 count を 0 で初期化する。
3. 各商品 \(i = 1, 2, \dots, N\) について以下を繰り返す：
   • 不良率 \(A_i\) と製造数 \(B_i\) を受け取る。
   • \(A_i \times B_i\) を計算し、その結果が \(K\) 以上であれば count に 1 を加える。
4. 最終的な count の値を出力する。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の商品に対してそれぞれ定数時間の計算（掛け算と比較）を行うため、商品の数に比例した時間がかかります。
• 空間計算量: \(O(N)\) 今回の実装では sys.stdin.read().split() を使用して全ての入力を一度にメモリに読み込んでいるため、入力サイズに比例したメモリを使用します。

実装のポイント

• 高速な入力処理: Pythonで \(N=2 \times 10^5\) 程度の入力を扱う場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込み、イテレータ（map や next）で処理することで、実行時間を大幅に短縮できます。

• 逐次処理: メモリ消費を抑えたい場合は、sys.stdin を 1 行ずつ読み込むことで、空間計算量を \(O(1)\) に抑えることも可能です。今回の制約ではどちらの方法でも正解できます。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、空白文字で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 整数への変換を効率的に行うため、mapを使用します
    it = map(int, input_data)
    
    # 商品の種類数 N と基準値 K を取得します
    try:
        N = next(it)
        K = next(it)
    except StopIteration:
        return
    
    count = 0
    # 各商品について、リスクスコアを計算して基準値 K と比較します
    for _ in range(N):
        try:
            a = next(it)
            b = next(it)
            # 問題文の定義に従い、リスクスコアは A_i * B_i です
            if a * b >= K:
                count += 1
        except StopIteration:
            break
            
    # 結果を出力します
    print(count)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。