概要

各商品のリスクスコア（不良率 × 製造数）を計算し、基準値 \(K\) 以上となる商品の数を数える問題です。

考察

この問題は、与えられた条件を満たす要素を単純にカウントする問題です。

重要な気づき

• 各商品について独立にリスクスコアを計算できる
• 商品間の関係性を考慮する必要がない
• 全ての商品を1回ずつ確認すれば答えが求まる

素朴なアプローチで問題ないか？

この問題では、\(N\) 個の商品それぞれについて1回ずつ判定すれば十分です。\(N \leq 2 \times 10^5\) なので、\(O(N)\) のアルゴリズムは十分高速に動作します。

注意点：オーバーフローについて

\(A_i\) は最大 \(100\)、\(B_i\) は最大 \(10^9\) なので、リスクスコア \(A_i \times B_i\) は最大で \(100 \times 10^9 = 10^{11}\) になります。これは32ビット整数の範囲（約 \(2 \times 10^9\)）を超えますが、Pythonでは整数のオーバーフローが発生しないため、特別な対策は不要です。（C++などでは long long 型を使う必要があります）

アルゴリズム

1. 商品数 \(N\) と基準値 \(K\) を読み込む
2. カウンター count を \(0\) で初期化
3. 各商品 \(i\) について以下を繰り返す：
   • 不良率 \(A_i\) と製造数 \(B_i\) を読み込む
   • リスクスコア \(A_i \times B_i\) を計算
   • リスクスコアが \(K\) 以上なら count を \(1\) 増やす
4. 最終的な count を出力

具体例

入力例として \(N = 3\), \(K = 100\) で、以下の商品があるとします： - 商品1: \(A_1 = 5\), \(B_1 = 30\) → リスクスコア = \(150\) ≥ \(100\) ✓ - 商品2: \(A_2 = 2\), \(B_2 = 40\) → リスクスコア = \(80\) < \(100\) ✗ - 商品3: \(A_3 = 10\), \(B_3 = 10\) → リスクスコア = \(100\) ≥ \(100\) ✓

答えは \(2\) となります。

計算量

• 時間計算量: \(O(N)\)
  • 各商品について定数時間の処理（入力読み込み、積の計算、比較）を行う
• 空間計算量: \(O(1)\)
  • カウンター変数と各商品のデータを保持する変数のみ使用
  • 全商品のデータを配列に保存する必要がない

実装のポイント

• 入力を1行ずつ処理しながらカウントすることで、メモリ使用量を抑えられる

• Pythonでは整数のオーバーフローを気にする必要がない

• 条件判定 A * B >= K は単純な比較で十分

  ソースコード

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)

---

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