概要

各科目について、現在の得点が合格点に満たない場合に必要な勉強時間を計算し、その合計を求める問題です。

考察

この問題のポイントは以下の通りです。

• 各科目は独立しています。ある科目の勉強が他の科目に影響を与えることはありません。
• 得点が合格点 \(T\) 以上の科目は勉強不要、\(T\) 未満の科目だけ勉強すればよいです。
• 科目 \(i\) で不足している点数は \(T - A_i\) 点であり、\(1\) 点上げるのに \(C_i\) 時間かかるので、その科目に必要な勉強時間は \((T - A_i) \times C_i\) です。

具体例で確認してみましょう。

例えば、\(N = 3\)、\(T = 80\) で以下のような入力があったとします：

• 科目1: \(60 < 80\) なので、\((80 - 60) \times 3 = 60\) 時間必要
• 科目2: \(90 \geq 80\) なので、勉強不要（\(0\) 時間）
• 科目3: \(70 < 80\) なので、\((80 - 70) \times 2 = 20\) 時間必要

合計: \(60 + 0 + 20 = 80\) 時間

この問題は各科目を順番に見ていくだけで解けるため、特別なアルゴリズムは不要です。素朴なアプローチがそのまま最適解となります。

アルゴリズム

1. \(N\) と \(T\) を読み込む。
2. 合計勉強時間を \(0\) で初期化する。
3. 各科目 \(i\) について、得点 \(A_i\) とコスト \(C_i\) を読み込む。
   • \(A_i < T\) ならば、不足分 \((T - A_i) \times C_i\) を合計に加算する。
   • \(A_i \geq T\) ならば、何もしない。
4. 合計勉強時間を出力する。

計算量

• 時間計算量: \(O(N)\) — 各科目を1回ずつ見るだけ
• 空間計算量: \(O(1)\) — 合計値を保持する変数のみ使用（入力を都度読み込むため配列不要）

実装のポイント

• \(A_i \geq T\) の場合に勉強時間を加算しないよう、if A < T の条件分岐を忘れないこと。もし条件なしに \((T - A_i) \times C_i\) を加算すると、\(A_i > T\) のとき負の値が加算されてしまい、誤った答えになります。

• 出力は最小合計勉強時間を 1行で 出力します。

  ソースコード

N, T = map(int, input().split())
total = 0
for _ in range(N):
    A, C = map(int, input().split())
    if A < T:
        total += (T - A) * C
print(total)

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