概要

各スマートフォンの初期バッテリー量と毎秒の消費量が与えられ、時刻 \(T\) における全スマートフォンのバッテリー残量の合計を求める問題。

考察

各スマートフォン \(i\) は初期バッテリー量 \(A_i\) を持ち、毎秒 \(B_i\) だけバッテリーを消費します。時刻 \(T\) において、単純には \(A_i - B_i \times T\) がそのバッテリー残量になりますが、これが負になることはなく、最低でも \(0\) になります。

つまり、時刻 \(T\) におけるスマートフォン \(i\) のバッテリー残量は以下のように表せます：

\[ \max(0, A_i - B_i \times T) \]

したがって、これをすべてのスマートフォンについて計算し、合計すれば答えとなります。

素朴なアプローチとして、各スマホについてこの計算を行うだけで十分であり、特に難しい処理は必要ありません。しかし、制約が \(N \leq 2 \times 10^5\)、\(T \leq 10^9\) と大きいため、効率的な入力処理が必要です。Python標準の input() を使用するとTLEになる可能性があるため、高速な入力方法（例：sys.stdin.read）を使用します。

アルゴリズム

1. すべての入力を一度に読み込む（高速化のため）。
2. 各スマートフォンについて、初期バッテリー量 \(A_i\) と消費速度 \(B_i\) を読み取りながら以下の計算を行う：
   • 時刻 \(T\) での消費量：\(B_i \times T\)
   • 残量：\(\max(0, A_i - B_i \times T)\)
3. 全てのスマートフォンの残量を合計して出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力データを除く）

実装のポイント

• 入力を高速に行うために sys.stdin.read を使用している。

• 各スマホの残量が負にならないよう、max(0, ...) を使う。

• 整数オーバーフローに注意（\(B_i \times T\) は最大 \(10^{18}\) 程度になり得るが、Pythonでは問題ない）。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    
    total = 0
    index = 2
    for _ in range(N):
        A = int(data[index])
        B = int(data[index+1])
        index += 2
        
        # 消費されるバッテリー量
        consumed = B * T
        
        # 残量は0未満にならない
        remaining = max(0, A - consumed)
        total += remaining
    
    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。