概要

地点 \(i\) に届ける手紙は、郵便局（地点 \(1\)）から地点 \(i\) まで運ぶ間ずっと手元に持ち続ける必要があり、その距離分だけ疲労度が発生します。全ての手紙について「通数 × 郵便局からの距離」を合計したものが答えになります。

考察

まず、疲労度がどのように発生するかを整理します。往路で地点 \(p\) から地点 \(p+1\) へ移動するとき、そのとき手元に持っている手紙の通数だけ疲労度が発生します。

ここで 1 通の手紙に注目 してみましょう。地点 \(i\) 宛ての手紙を届けるには、必ず郵便局（地点 \(1\)）から地点 \(i\) まで手元に持って移動する必要があります。この間に通過する辺は

\[1 \to 2,\quad 2 \to 3,\quad \ldots,\quad (i-1) \to i\]

の \(i-1\) 本です。この手紙は、これらすべての移動の際に「手元に持っている手紙」として数えられるため、1 通あたり必ず \(i-1\) の疲労度を生み出します。これは地点 \(1\) から地点 \(i\) までの距離 \(i-1\) に等しいです。

重要なのは、この疲労度は運び方を工夫しても減らせないという点です。手紙を届けるには必ず目的地まで運ぶしかなく、途中で疲労度を回避する方法はありません。また、帰路では疲労度が発生しないので、余計な移動を増やさなければ損もしません。

したがって、複数回に分けて配達しても、まとめて配達しても、疲労度の合計は変わりません。地点 \(i\) 宛ての \(B_i\) 通の手紙が生む疲労度は必ず

\[B_i \times (i-1)\]

となり、全体の最小値は

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

で与えられます。

素朴に「どのルートでどの手紙を運ぶか」を全探索するようなアプローチを考えたくなるかもしれませんが、上記の観察により ルートの組み方は答えに影響しない ため、単純な総和計算だけで済みます。

具体例で確認してみましょう。\(N=3\)、\(B_2=2\)、\(B_3=3\) の場合： - 地点 \(2\) 宛ての手紙は距離 \(1\) を運ぶので \(2 \times 1 = 2\) - 地点 \(3\) 宛ての手紙は距離 \(2\) を運ぶので \(3 \times 2 = 6\) - 合計 \(8\)

アルゴリズム

各地点 \(i\)（\(2 \leq i \leq N\)）について、\(B_i\) に距離 \((i-1)\) を掛けた値を足し合わせるだけです。

入力の配列 data[1..n-1] は \(B_2, B_3, \ldots, B_N\) に対応します。\(j\) 番目（\(j=0,1,\ldots\)）の要素は地点 \(2+j\) 宛てなので、その距離は \((2+j)-1 = j+1\) です。よって

\[\text{ans} = \sum_{j=0}^{N-2} (j+1) \times B_{2+j}\]

を計算します。

計算量

• 時間計算量: \(O(N)\)（配列を一度走査するだけ）
• 空間計算量: \(O(N)\)（入力を保持する分）

実装のポイント

• \(N\) が最大 \(10^6\)、\(B_i\) が最大 \(10^7\)、距離が最大 \(10^6\) 程度になるため、合計値は 32-bit 整数の範囲を超えます。C++ などでは 64-bit 整数（long long）を使う必要があります。Python では整数が自動的に多倍長になるため気にする必要はありません。

• \(N\) が大きいため、入力の読み込みは高速に行うのが安全です。本コードでは sys.stdin.buffer.read() でまとめて読み込んでから処理しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    ans = 0
    # data[1..n-1] が B_2..B_N（計 n-1 個）
    # 地点 2+j (j=0..) までの距離は j+1
    for j in range(n - 1):
        ans += (j + 1) * int(data[1 + j])
    sys.stdout.write(str(ans) + "\n")

main()

---

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