概要

各科目の得点が合格点 \(T\) に届くまでに必要な「不足点数 × 1点あたりの勉強時間」を合計し、最小の総勉強時間を求める問題です。

考察

重要な観察は「科目ごとに必要な勉強時間が独立して決まる」ことです。
科目 \(i\) の得点が \(A_i < T\) なら、必要な追加点数は \(T - A_i\) 点であり、1点上げるのに \(C_i\) 時間かかるので、その科目に必要な時間は - \((T - A_i) \times C_i\) で一意に決まります。逆に \(A_i \ge T\) なら追加勉強は不要で \(0\) 時間です。

ここで「どの科目から勉強するか」「時間配分を工夫するか」といった最適化は一切不要です。なぜなら、各科目の不足点数は必ず埋める必要があり、他の科目の勉強が不足分を肩代わりすることはできないからです。

素朴に「1点ずつ増やしてシミュレーション」すると、最大で各科目 \(10^4\) 点分 × \(10^5\) 科目となり、最悪 \(10^9\) 回程度の操作になって非現実的（TLE）です。
不足点数をまとめて掛け算で計算すれば、各科目1回の処理で済みます。

（例）\(T=80\)、ある科目が \(A=75, C=3\) なら不足は \(5\) 点なので必要時間は \(5\times3=15\)。これを全科目で足し合わせます。

アルゴリズム

1. 入力で \(N, T\) を受け取る。
2. 合計時間 total = 0 を用意する。
3. 各科目について \((A_i, C_i)\) を読み込み、
   • もし \(A_i < T\) なら total += (T - A_i) * C_i
   • そうでなければ何もしない（追加 \(0\)）
4. total を出力する。

計算量

• 時間計算量: \(O(N)\)（各科目を1回ずつ処理）
• 空間計算量: \(O(1)\)（合計値など定数個のみ）

実装のポイント

• 合計は最大で \((T-A_i)\le 10^4\), \(C_i\le 10^4\), \(N\le 10^5\) より、最大 \(10^4 \times 10^4 \times 10^5 = 10^{13}\) 程度になり得ます。Python の int は任意精度なのでそのままで安全です。

• 入力が多いので sys.stdin.readline を使うと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    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)

if __name__ == "__main__":
    main()

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