概要

各科目の現在の得点と1点上げるのに必要な勉強時間が与えられ、すべての科目を合格点以上にするために必要な最小の合計勉強時間を求める問題です。

考察

各科目について、現在の得点 \(A_i\) が合格点 \(T\) に満たない場合のみ、追加の勉強が必要です。必要な得点アップ量は \((T - A_i)\) 点であり、これに単位勉強時間 \(C_i\) を掛けることで、その科目に必要な勉強時間が計算できます。すでに合格点以上の科目は勉強時間が0となるため、単純に不合格科目だけを計算すれば十分です。

アルゴリズム

1. 入力から科目数 \(N\) と合格点 \(T\) を読み取る
2. 各科目について \(A_i\) と \(C_i\) を読み取る
3. 各科目について:
   • \(A_i < T\) の場合: 必要な得点アップ量 \((T - A_i)\) と \(C_i\) の積を合計勉強時間に加算する
   • \(A_i \geq T\) の場合: 何も加算しない（勉強不要）
4. 合計勉強時間を出力する

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 科目分のデータを処理するため
• 空間計算量: \(O(1)\)
  • 入力データを逐次処理し、追加のメモリをほとんど使用しない

実装のポイント

• 入力データを一度に読み取ってから処理することで効率的な入出力が可能

• 各科目の処理時に、合格点未満かどうかのみを判定すればよく、シンプルな実装になる

• 整数型で処理できるため、型変換に注意

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    A = []
    C = []
    index = 2
    total_time = 0
    for i in range(n):
        a = int(data[index])
        c = int(data[index+1])
        index += 2
        if a < T:
            needed = T - a
            total_time += needed * c
    print(total_time)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。