概要

地点 \(1\)（郵便局）から出発し、一直線上に並ぶ各地点に指定された数の手紙を届けるときの、総疲労度の最小値を求める問題です。一見すると「何回に分けて運ぶか」などの複雑な組み合わせを考える必要があるように見えますが、手紙 \(1\) 通あたりに必要な最小の疲労度に着目することで、非常にシンプルな数式で解くことができます。

考察

1. 手紙 \(1\) 通あたりに必要な最小の疲労度

地点 \(i\) （\(2 \leq i \leq N\)）宛ての手紙 \(1\) 通に着目します。 この手紙を無事に目的地に届けるためには、少なくとも \(1\) 回は地点 \(1\) から地点 \(i\) まで運ぶ必要があります。

地点 \(1\) から地点 \(i\) の間には、\((i-1)\) 個の隣り合う地点間の区間（\([1, 2], [2, 3], \ldots, [i-1, i]\)）があります。手紙を届けるためには、これらの区間を少なくとも \(1\) 回ずつは通過しなければなりません。手紙が区間を \(1\) 回通過するたびに疲労度が \(1\) 発生するため、地点 \(i\) 宛ての手紙 \(1\) 通を届けるために発生する疲労度は、どのようなルートをたどっても最低限 \(i-1\) 必要になります。

したがって、すべての手紙を届けるために必要な総疲労度は、どう工夫しても以下の値（下限値）より小さくすることはできません。 $\(\sum_{i=2}^{N} B_i \times (i - 1)\)$

2. 下限値が実際に達成できるかの検証

では、この下限値である \(\sum_{i=2}^{N} B_i \times (i - 1)\) を実際に達成する配達ルートは存在するでしょうか。

実は、「最初の \(1\) 回のルートで、すべての手紙をまとめて持って出発し、各地点を通り過ぎるたびにその地点宛ての手紙をすべて配る」というシンプルな戦略をとることで、この下限値をぴったり達成できます。

この戦略をとったとき、地点 \(i\) 宛ての手紙は地点 \(1\) から地点 \(i\) まで一度も引き返すことなく運ばれます。そのため、各区間 \([p, p+1]\) (\(p < i\)) を通過する回数はちょうど \(1\) 回となり、この手紙によって発生する疲労度は正確に \(i-1\) になります。

具体例 (\(N=3, B_2=2, B_3=3\))

• 地点 \(2\) 宛ての手紙は \(2\) 通（それぞれ最低 \(2-1 = 1\) の疲労度が必要）
• 地点 \(3\) 宛ての手紙は \(3\) 通（それぞれ最低 \(3-1 = 2\) の疲労度が必要）
• 理論上の最小疲労度（下限値）は、 \(2 \times 1 + 3 \times 2 = 8\) です。

すべての手紙（計 \(5\) 通）を持って出発する場合のシミュレーション： 1. 出発： 手紙を \(5\) 通持って地点 \(1\) を出発。 2. 移動 \(1 \to 2\)： 手元に \(5\) 通あるため、疲労度が \(5\) 発生。地点 \(2\) に到着し、地点 \(2\) 宛ての手紙 \(2\) 通を配る（手元に残る手紙は \(3\) 通）。 3. 移動 \(2 \to 3\)： 手元に \(3\) 通あるため、疲労度が \(3\) 発生。地点 \(3\) に到着し、地点 \(3\) 宛ての手紙 \(3\) 通を配る（手元に残る手紙は \(0\) 通）。 4. 帰路： 帰路の疲労度は \(0\)。

発生した総疲労度は \(5 + 3 = 8\) となり、理論上の下限値と一致します。

したがって、求める最小値は常に \(\sum_{i=2}^{N} B_i \times (i - 1)\) となります。

アルゴリズム

1. 総疲労度を表す変数 total_fatigue を \(0\) で初期化します。
2. \(i = 2, 3, \ldots, N\) について、入力を順に受け取ります。
3. 地点 \(i\) の手紙の数 \(B_i\) に対し、B_i * (i - 1) を計算して total_fatigue に加算します。
4. 最終的な total_fatigue の値を出力します。

計算量

• 時間計算量: \(O(N)\) 各地点の情報を \(1\) 回ずつ走査して計算を行うため、地点数 \(N\) に対して線形時間で動作します。
• 空間計算量: \(O(1)\) 入力を配列などに保持せず、その都度処理して足し合わせることで、余分なメモリを使用せずに計算できます。

実装のポイント

• オーバーフローの防止: \(N\) は最大で \(10^6\)、各 \(B_i\) は最大で \(10^7\) です。 答えの最大値は、およそ \(\sum_{i=2}^{10^6} 10^7 \times i \approx 10^7 \times \frac{(10^6)^2}{2} \approx 5 \times 10^{18}\) となり、通常の 32-bit 整数型（int）の最大値（約 \(2 \times 10^9\)）を大きく超えます。そのため、計算および答えの保持には必ず 64-bit 整数型（C++ の long long）を使用してください。

• 入出力の高速化: \(N\) が最大 \(10^6\) と大きいため、C++ では std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); を用いて入出力を高速化しておくことで、実行時間を大幅に短縮できます。

  ソースコード

#include <iostream>

using namespace std;

int main() {
    // Optimize input/output operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    long long total_fatigue = 0;
    for (int i = 2; i <= N; ++i) {
        long long B;
        cin >> B;
        total_fatigue += B * (i - 1);
    }

    cout << total_fatigue << "\n";

    return 0;
}

---

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