概要

各地点 \(i\) へ届ける手紙は、必ず郵便局（地点 \(1\)）から地点 \(i\) まで運ばれる必要があり、\(1\) 通あたり移動距離 \(i-1\) 分の疲労度が必ず発生します。したがって答えは \(\sum_{i=2}^{N} (i-1) \times B_i\) となります。

考察

重要な気づき

まず「疲労度」の定義を丁寧に見直しましょう。往路で地点 \(p\) から \(p+1\) へ移動するとき、そのときに手元に持っている手紙の通数だけ疲労度が発生します。

ここで、\(1\) 通の手紙に着目してみます。地点 \(i\) 宛ての手紙 \(1\) 通は、郵便局（地点 \(1\)）から地点 \(i\) まで運ばれる間、ずっと手元にあります。つまりこの手紙は、 - 地点 \(1 \to 2\) の移動 - 地点 \(2 \to 3\) の移動 - \(\ldots\) - 地点 \((i-1) \to i\) の移動

という \(i-1\) 回の移動すべてで手元に存在し、それぞれの移動で「\(+1\)」の疲労度を発生させます。

つまり、地点 \(i\) 宛ての手紙 \(1\) 通は、どんな運び方をしても必ず疲労度 \(i-1\) を発生させるのです。

ルートの分け方は関係ない

「同じ地点宛ての手紙を複数回に分ける」「一度に複数の地点宛ての手紙を持つ」といった自由度がありますが、実は疲労度の合計には一切影響しません。

なぜなら、疲労度の合計を「手紙 \(1\) 通ごと」に分解して考えると、各手紙が寄与する疲労度は運び方に依存せず「その手紙が越える辺の本数 = 目的地までの距離」で固定されるからです。複数の手紙を同時に運んでも、疲労度は各手紙の寄与の単純な合計になります（\(1\) 回の移動で \(k\) 通持っていれば疲労度 \(k\) = \(1\) 通ずつの寄与 \(1\) を \(k\) 個足したもの）。

したがって、どのようなルート構成でも合計疲労度は変わらず、

\[ \text{答え} = \sum_{i=2}^{N} (i-1) \times B_i \]

と一意に定まります。最小値を探すために工夫する必要はありません。

具体例

例えば \(N=4\)、\(B_2=2, B_3=1, B_4=3\) のとき： - 地点 \(2\) 宛て：\(2\) 通 × 距離 \(1\) = \(2\) - 地点 \(3\) 宛て：\(1\) 通 × 距離 \(2\) = \(2\) - 地点 \(4\) 宛て：\(3\) 通 × 距離 \(3\) = \(9\)

合計 \(2 + 2 + 9 = 13\) が答えです。

アルゴリズム

上記の式を単純に計算するだけです。

1. \(N\) と \(B_2, \ldots, B_N\) を読み込む。
2. 各 \(i\) について \((i-1) \times B_i\) を加算していく。
3. 合計を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を逐次処理すれば追加の配列は不要）

実装のポイント

• オーバーフローに注意：\(N \leq 10^6\)、\(B_i \leq 10^7\) なので、\((i-1) \times B_i\) は最大で約 \(10^6 \times 10^7 = 10^{13}\)、それを \(N\) 個足すと最大 \(10^{19}\) 近くになりそうに見えますが、制約より答えは signed 64-bit integer（最大約 \(9.2 \times 10^{18}\)）に収まることが保証されています。いずれにせよ int では確実にあふれるため、C++ では long long を使いましょう。

• 入力の高速化：\(N\) が最大 \(10^6\) と大きいため、cin そのままだと遅くなる場合があります。本コードでは fread によるバッファ読み込みと自前の整数パーサを用いて高速化しています。scanf や ios::sync_with_stdio(false) でも十分間に合うことが多いです。

• 手紙の途中保管や分割配達といった問題文中の複雑な設定は、最終的な答えには影響しないという点を見抜けるかどうかが本問の核心です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 高速入力
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    auto readInt = [&]() -> long long {
        while (pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if (pos < len && buf[pos] == '-') { neg = true; pos++; }
        long long x = 0;
        while (pos < len && buf[pos] >= '0' && buf[pos] <= '9') {
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };

    long long N = readInt();
    long long ans = 0;
    for (long long i = 2; i <= N; i++) {
        long long b = readInt();
        ans += (i - 1) * b;
    }
    printf("%lld\n", ans);
    return 0;
}

---

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