概要

\(N\) 本の植物について、それぞれの「現在の高さ」と「1日あたりの成長量」が与えられたとき、\(D\) 日後のすべての植物の高さの合計を求める問題です。

考察

\(i\) 番目の植物に注目すると、現在の高さは \(A_i\)、1日あたりの成長量は \(B_i\) です。 したがって、\(D\) 日後における \(i\) 番目の植物の高さ \(H_i\) は、以下の式で表せます。 $\(H_i = A_i + (B_i \times D)\)$

私たちが求めたいのは、すべての植物の高さの合計 \(S\) です。 $\(S = \sum_{i=1}^{N} H_i = \sum_{i=1}^{N} (A_i + B_i \times D)\)$

この式は、数学の分配法則（あるいは和の記号 \(\sum\) の性質）を用いると、以下のように変形できます。 $\(S = (\sum_{i=1}^{N} A_i) + D \times (\sum_{i=1}^{N} B_i)\)$

つまり、「現在の高さの合計」と「1日あたりの成長量の合計」をそれぞれ計算しておけば、最後に \(D\) を掛けて足し合わせるだけで答えが求まります。

\(N\) は最大 \(10^5\) であるため、各植物について計算を行うループを1回回すだけで十分に間に合います。また、答えの最大値は \(2 \times 10^{16}\) と非常に大きくなりますが、Pythonなどの多倍長整数を扱う言語や、C++の long long 型などを用いれば、精度を保ったまま計算可能です。

アルゴリズム

1. 現在の高さの合計を保持する変数 sum_a と、成長量の合計を保持する変数 sum_b を \(0\) で初期化します。
2. 植物 \(1\) から \(N\) まで順番に以下の処理を行います。
   • sum_a に \(A_i\) を加算する。
   • sum_b に \(B_i\) を加算する。
3. 最終的な答えを sum_a + D * sum_b として計算し、出力します。

計算量

• 時間計算量: \(O(N)\)
  • 植物の数 \(N\) に比例した回数の加算処理を行うため、非常に高速に動作します。
• 空間計算量: \(O(N)\)
  • sys.stdin.read().split() を使用して入力を一度にリストとして読み込む場合、入力サイズに比例したメモリを消費します。

実装のポイント

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

• オーバーフローの回避: 答えが \(2 \times 10^{16}\) に達するため、プログラミング言語によっては 64bit 整数型（long long など）を使用する必要があります。Pythonの場合は標準の int 型が自動的に大きな値を扱えるため、特に意識せず計算できます。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、空白で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 植物の本数, D: 経過日数
    N = int(data[0])
    D = int(data[1])
    
    sum_a = 0
    sum_b = 0
    
    # 各植物の現在の高さ A_i と1日あたりの成長量 B_i を集計する
    # data[2 + 2*i] が A_i, data[3 + 2*i] が B_i に対応する
    for i in range(N):
        sum_a += int(data[2 + 2 * i])
        sum_b += int(data[3 + 2 * i])
    
    # D日後の合計高さ = (現在の高さの合計) + D * (1日あたりの成長量の合計)
    ans = sum_a + D * sum_b
    print(ans)

if __name__ == '__main__':
    solve()

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