概要

\(N\) 個の科目について、すべての得点を合格点 \(T\) 以上にするために必要な勉強時間の合計を求める問題です。各科目 \(i\) において、得点が \(T\) に満たない場合にのみ、不足分を補うための勉強時間を計算します。

考察

この問題を解くためのポイントは、「各科目は独立している」という点です。ある科目の得点を上げることが他の科目の得点に影響しないため、各科目について個別に「合格点に達するために必要な最小時間」を計算し、それらをすべて足し合わせることで全体の最小時間を求めることができます。

具体的に、科目 \(i\) について必要な勉強時間を考えてみましょう。 - 現在の得点 \(A_i\) が合格点 \(T\) 以上の場合 (\(A_i \geq T\)) すでに合格点に達しているため、追加の勉強時間は \(0\) です。 - 現在の得点 \(A_i\) が合格点 \(T\) 未満の場合 (\(A_i < T\)) 合格点に達するためには、あと \(T - A_i\) 点必要です。\(1\) 点上げるのに \(C_i\) 時間かかるため、この科目に必要な勉強時間は \((T - A_i) \times C_i\) となります。

例えば、\(T=80, A_i=75, C_i=10\) の場合、不足している \(5\) 点分を補うために \(5 \times 10 = 50\) 時間が必要になります。

アルゴリズム

以下の手順で計算を行います。

1. 合計勉強時間を保持する変数 total_study_time を \(0\) で初期化する。
2. 各科目 \(i = 1, 2, \dots, N\) について以下を繰り返す：
   • もし \(A_i < T\) ならば、total_study_time に \((T - A_i) \times C_i\) を加算する。
   • そうでなければ（すでに合格点以上なら）、何もしない。
3. 最終的な total_study_time の値を出力する。

計算量

• 時間計算量: \(O(N)\) 科目数 \(N\) に対して \(1\) 回ずつループを回して計算を行うため、入力の大きさに比例した時間で処理が完了します。\(N = 10^5\) であっても、現代のコンピュータでは十分に高速に動作します。
• 空間計算量: \(O(N)\) 今回の実装では sys.stdin.read().split() を用いてすべての入力を一度にリストとして読み込んでいるため、入力データ量に比例したメモリを使用します。

実装のポイント

• 大きな数値の扱い: 答えとなる合計勉強時間は最大で \(10^5 \times 10^4 \times 10^4 = 10^{13}\) 程度になる可能性があります。Pythonでは整数の大きさに制限がないため問題ありませんが、他の言語（C++など）を使用する場合は、32bit整数型（int）ではなく64bit整数型（long longなど）を使用する必要があります。

• 高速な入出力: \(N\) が \(10^5\) と大きいため、科目ごとに input() を呼び出すよりも、sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できる場合があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 科目数 N と合格点 T を取得します
    N = int(input_data[0])
    T = int(input_data[1])
    
    total_study_time = 0
    
    # 各科目の得点 A_i と勉強時間 C_i を処理します
    for i in range(N):
        # A_i は input_data の 2 + 2*i 番目、C_i は 3 + 2*i 番目にあります
        a = int(input_data[2 + 2 * i])
        c = int(input_data[3 + 2 * i])
        
        # 得点が合格点 T 未満の場合、必要な勉強時間を加算します
        if a < T:
            needed_points = T - a
            total_study_time += needed_points * c
            
    # 合計勉強時間を出力します
    print(total_study_time)

if __name__ == '__main__':
    solve()

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