概要

\(N\) 台のスマートフォンが時刻 \(T\) でどれだけバッテリーが残っているかを計算し、その合計を求める問題です。

考察

重要な気づき

各スマートフォンについて、時刻 \(T\) におけるバッテリー残量は独立に計算できます。

スマートフォン \(i\) のバッテリー残量を考えると： - 初期残量: \(A_i\) mAh - \(T\) 秒間の消費量: \(B_i \times T\) mAh

単純に計算すると \(A_i - B_i \times T\) となりますが、バッテリー残量は \(0\) 以下にはならないという条件があります。

具体例で確認

例えば、\(A = 100\), \(B = 3\), \(T = 50\) の場合： - 消費量は \(3 \times 50 = 150\) mAh - 単純計算では \(100 - 150 = -50\) mAh - しかし、実際には途中でバッテリーが切れるので、残量は \(0\) mAh

逆に、\(A = 100\), \(B = 1\), \(T = 50\) の場合： - 消費量は \(1 \times 50 = 50\) mAh - 残量は \(100 - 50 = 50\) mAh

素朴なアプローチとの比較

「毎秒シミュレーションする」方法を考えると、\(T\) が最大 \(10^9\) なので、\(N \times T\) 回の計算が必要になり TLE になります。

しかし、各スマートフォンの残量は 直接計算 できるため、シミュレーションは不要です。

アルゴリズム

1. 各スマートフォン \(i\) について、時刻 \(T\) での残量を計算する
2. 残量は \(\max(0, A_i - B_i \times T)\) で求められる
3. 全スマートフォンの残量を合計して出力する

\(\max\) 関数を使うことで、負の値になる場合は \(0\) に置き換えています。

計算量

• 時間計算量: \(O(N)\)
  • 各スマートフォンについて定数時間の計算を行うため
• 空間計算量: \(O(1)\)
  • 合計値を保持する変数のみ使用

実装のポイント

1. オーバーフローに注意: \(B_i \times T\) は最大で \(10^9 \times 10^9 = 10^{18}\) になる可能性があります。Python では整数のオーバーフローがないため問題ありませんが、C++ などでは long long 型を使う必要があります。

2. max(0, ...) の使用: バッテリー残量が負にならないことを保証するため、max 関数で \(0\) との最大値を取ります。

3. 入力の読み込み: \(N\) 回のループで各スマートフォンの情報を読み込みながら、同時に残量を計算・加算することで、メモリ効率よく処理できます。

   ソースコード

N, T = map(int, input().split())
total = 0
for _ in range(N):
    A, B = map(int, input().split())
    remaining = max(0, A - B * T)
    total += remaining
print(total)

---

この解説は claude4.5opus によって生成されました。