概要

一直線上に並んだ地点に手紙を届ける際、手紙を目的地まで運ぶために発生する疲労度の合計最小値は、各手紙が郵便局から目的地までの距離に比例して疲労度を消費することから、非常にシンプルな式で求まります。

考察

この問題では、手紙をどのタイミングで、どのルートで届けるかが重要に思えますが、実は疲労度の合計は届け方に依存しません。

地点 \(i\) 宛ての手紙 1 通を届けるためには、必ず地点 1 から地点 \(i\) まで移動する必要があります。移動時の疲労度は「持っている手紙の通数」に等しいため、この手紙 1 通は移動する各区間（\(1 \to 2\), \(2 \to 3\), \(\ldots\), \(i-1 \to i\)）でそれぞれ 1 ずつ疲労度を発生させます。つまり、地点 \(i\) 宛ての手紙 1 通あたりの疲労度は合計で \(i-1\) となります。

手紙を複数回のルートに分けて届けたり、他の地点宛ての手紙と一緒にまとめて運んだりしても、地点 \(i\) 宛ての手紙が地点 1 から地点 \(i\) までの各区間を通過するという事実は変わりません。したがって、地点 \(i\) 宛ての手紙 \(B_i\) 通は必ず合計で \((i-1) \times B_i\) の疲労度を発生させます。

よって、全ての手紙を届けるための疲労度の合計は、各地点について \((i-1) \times B_i\) を計算し、それらをすべて足し合わせるだけで求まります。

アルゴリズム

地点の数 \(N\) と各地点 \(i\)（\(2 \leq i \leq N\)）に届ける手紙の通数 \(B_i\) が与えられます。

1. 答えを格納する変数（long long 型など）を 0 で初期化する。
2. \(i = 2\) から \(N\) までループを回し、答えに \((i - 1) \times B_i\) を足し合わせる。
3. 計算した合計値を出力する。

このアルゴリズムはただの1重ループであり、計算量も少なく、非常に高速に動作します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力を配列に格納する場合。入力を受け取りながら逐次計算すれば \(O(1)\) にもできます）

実装のポイント

• \(N\) が最大 \(10^6\)、\(B_i\) が最大 \(10^7\) であるため、答えが 32-bit 整数型（int など）の範囲を超える可能性があります。答えを格納する変数や計算時の型として 64-bit 整数型（long long など）を使用するように注意してください。

• 提出されたコードでは、C++の入力高速化（ios_base::sync_with_stdio(false); cin.tie(NULL);）を適用していますが、\(N \le 10^6\) の入力を高速に処理するために有用です。また、配列の代わりにその場で計算して足し合わせることで、空間計算量を \(O(1)\) に削減することも可能です。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> B(N + 1, 0);
    for (int i = 2; i <= N; ++i) {
        cin >> B[i];
    }
    
    long long ans = 0;
    for (int i = 2; i <= N; ++i) {
        ans += (long long)(i - 1) * B[i];
    }
    
    cout << ans << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。