概要

各植物について、\(D\) 日後の高さは「現在の高さ \(A_i\)」に「\(D\) 日分の成長量 \(D \times B_i\)」を足したものです。
それを全ての植物について足し合わせれば答えになります。

考察

この問題で求めたいのは、\(D\) 日後の \(N\) 本の植物の高さの合計です。

まず、1本の植物に注目すると、現在の高さが \(A_i\) mm、1日あたり \(B_i\) mm 伸びるので、\(D\) 日後の高さは

\(A_i + D \times B_i\)

となります。

したがって、全体の合計は

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

です。

重要な気づき

「1日ずつシミュレーションする必要はない」というのがこの問題のポイントです。

例えば、素朴に - 1日目に全植物を伸ばす - 2日目に全植物を伸ばす - … - \(D\) 日目まで繰り返す

という方法を考えると、計算量は \(O(ND)\) になります。

制約では - \(N \le 10^5\) - \(D \le 10^6\)

なので、最悪で \(10^{11}\) 回程度の計算が必要になり、これは現実的ではありません。

しかし、各植物の成長は一定なので、\(D\) 日後の高さを直接計算できます。
これにより、各植物について1回ずつ計算するだけで済みます。

具体例

例えば、\(A=10\), \(B=3\), \(D=5\) の植物なら、

• 1日後: \(13\)
• 2日後: \(16\)
• 3日後: \(19\)
• 4日後: \(22\)
• 5日後: \(25\)

ですが、これは最初から

\(10 + 5 \times 3 = 25\)

と一発で求められます。

アルゴリズム

1. \(N\) と \(D\) を入力する。
2. 合計値 total を \(0\) で初期化する。
3. 各植物について、現在の高さ \(A\) と1日あたりの成長量 \(B\) を読む。
4. その植物の \(D\) 日後の高さ \(A + D \times B\) を total に加える。
5. 最後に total を出力する。

この方法なら、全植物を1回ずつ見るだけで答えが求まります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 各植物について A + D * B をそのまま足し込めばよいです。

• 答えは大きくなる可能性がありますが、問題文で \(2 \times 10^{16}\) を超えないことが保証されています。

• Python の整数型は大きな値も扱えるので、そのままで問題ありません。

• 入力が多いので、sys.stdin.readline を使うと高速に処理できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    total = 0
    for _ in range(N):
        A, B = map(int, input().split())
        total += A + D * B
    print(total)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。