概要

\(N\) 本の植物それぞれについて \(D\) 日後の高さを求め、その合計を出力する問題です。

考察

\(i\) 番目の植物は現在の高さが \(A_i\) で、1日あたり \(B_i\) ミリメートルずつ成長します。したがって、\(D\) 日後の高さは次の式で表せます。

\[A_i + B_i \times D\]

例えば、現在の高さが \(10\) mm で1日あたり \(3\) mm 成長する植物の場合、\(5\) 日後の高さは \(10 + 3 \times 5 = 25\) mm です。

\(N\) 本の植物の高さの合計は次のようになります。

\[\sum_{i=1}^{N} (A_i + B_i \times D)\]

この問題では「1日ずつシミュレーションする」素朴なアプローチを考える人もいるかもしれません。つまり、\(D\) 日分のループを回し、毎日すべての植物の高さを更新する方法です。この場合、計算量は \(O(N \times D)\) となり、\(N = 10^5\)、\(D = 10^6\) のとき \(10^{11}\) 回の演算が必要になり、TLE（時間超過） になります。

しかし、成長量は一定なので、\(D\) 日後の高さは掛け算一回で直接計算できます。1日ずつシミュレーションする必要はありません。

アルゴリズム

1. 合計値を保持する変数 total を \(0\) で初期化する。
2. 各植物 \(i\) について、\(D\) 日後の高さ \(A_i + B_i \times D\) を total に加算する。
3. total を出力する。

具体例（入力例）:

3 2
10 5
20 3
15 8

• 植物1: \(10 + 5 \times 2 = 20\)
• 植物2: \(20 + 3 \times 2 = 26\)
• 植物3: \(15 + 8 \times 2 = 31\)
• 合計: \(20 + 26 + 31 = 77\)

計算量

• 時間計算量: \(O(N)\) — 各植物について1回ずつ計算するだけ
• 空間計算量: \(O(1)\) — 合計値を保持する変数のみ使用

実装のポイント

• オーバーフローに注意: \(A_i\) は最大 \(10^9\)、\(B_i \times D\) は最大 \(10^5 \times 10^6 = 10^{11}\)、これが \(N = 10^5\) 本分あるため、合計は最大約 \(10^{16}\) 程度になります。Python では整数のオーバーフローは発生しませんが、C++ などを使う場合は long long 型を使う必要があります。

• シミュレーション不要: 等速で成長するため、\(D\) 日後の高さは \(A_i + B_i \times D\) で直接求められます。ループで1日ずつ進める必要はありません。

  ソースコード

N, D = map(int, input().split())
total = 0
for _ in range(N):
    a, b = map(int, input().split())
    total += a + b * D
print(total)

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