概要

\(N\) 台のスマートフォンがあり、それぞれ初期バッテリー残量 \(A_i\) と、1秒あたりの消費量 \(B_i\) が決まっています。時刻 \(T\) における各スマートフォンの残量を計算し、その合計値を求める問題です。ただし、バッテリー残量は \(0\) 未満にはならない点に注意が必要です。

考察

各スマートフォンは独立してバッテリーを消費するため、1台ずつ順番に残量を計算していくことができます。

時刻 \(T\) におけるスマートフォン \(i\) のバッテリー消費量は \(B_i \times T\) となります。したがって、単純に計算すると時刻 \(T\) での残量は \(A_i - (B_i \times T)\) です。

ここで、問題文にある「バッテリー残量が \(0\) mAh になると、そのスマートフォンは電源が切れて消費が止まる（負の値にはならない）」という条件が重要になります。 - もし \(A_i - (B_i \times T) > 0\) であれば、そのままその値が残量となります。 - もし \(A_i - (B_i \times T) \leq 0\) であれば、途中でバッテリーが切れたことを意味するため、残量は \(0\) となります。

これを数式で表すと、スマートフォン \(i\) の時刻 \(T\) における残量は \(\max(0, A_i - B_i \times T)\) となります。

アルゴリズム

1. 合計残量を保持する変数 total_remaining を \(0\) で初期化します。
2. \(N\) 台のスマートフォンについて、以下の処理を繰り返します。
   • 時刻 \(T\) での計算上の残量 remaining = A_i - B_i * T を求めます。
   • remaining が \(0\) より大きい場合のみ、total_remaining にその値を加算します。
3. 最終的な total_remaining を出力します。

計算量

• 時間計算量: \(O(N)\)
  • スマートフォンの台数 \(N\) に対して、1回ずつ計算を行うため、入力の読み込みを含めて \(N\) に比例した時間で処理が終わります。\(N \leq 2 \times 10^5\) であるため、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • sys.stdin.read().split() を使用して入力を一括でリストに格納しているため、入力サイズに比例したメモリを使用します。

実装のポイント

• 大きな値の処理: バッテリーの合計値は非常に大きな値になる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフロー（桁あふれ）を気にせずに計算できます。

• 高速な入力: \(N\) が大きいため、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込むことで、実行時間を短縮しています。

• 条件分岐: remaining が負になる場合は加算しない（または \(0\) を加算する）という処理を忘れないようにします。

  ソースコード

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_remaining = 0
    
    # 各スマートフォンの初期残量 A と消費量 B を処理
    for i in range(N):
        A = int(input_data[2 + 2 * i])
        B = int(input_data[3 + 2 * i])
        
        # 時刻 T における残量を計算 (負になる場合は 0)
        remaining = A - B * T
        if remaining > 0:
            total_remaining += remaining
            
    # 合計を出力
    print(total_remaining)

if __name__ == '__main__':
    solve()

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