概要

地点 \(i\) 宛ての手紙は、必ず \(i-1\) 本の辺を通る必要があります。したがって、最小疲労度は各地点について「手紙の通数 \(\times\) 郵便局からの距離」を合計すれば求められます。

考察

地点 \(i\) 宛ての手紙を 1 通だけ考えます。

この手紙を届けるためには、往路で必ず

• 地点 \(1\) から地点 \(2\)
• 地点 \(2\) から地点 \(3\)
• \(\ldots\)
• 地点 \(i-1\) から地点 \(i\)

という \(i-1\) 回の移動を行わなければなりません。

これらの移動中、その手紙はまだ届けられておらず、手元に残っています。そのため、各移動で疲労度を \(1\) ずつ発生させ、合計で必ず \(i-1\) の疲労度を発生させます。

よって、地点 \(i\) に届ける手紙が \(B_i\) 通なら、それらが発生させる疲労度は少なくとも

\[ (i-1)B_i \]

です。

この下限は実際に達成できます。例えば、すべての手紙を一度に持って最も遠い必要地点まで進み、各地点に到着したときにその地点宛ての手紙をすべて届ければよいです。各手紙は届け先までだけ運ばれ、それより先へ運ばれることはありません。

したがって、答えは

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

となります。

例えば、\(B_2=2,\ B_3=1,\ B_4=0,\ B_5=3\) の場合は、

\[ 1 \times 2 + 2 \times 1 + 3 \times 0 + 4 \times 3 = 16 \]

です。

配達ルートの分け方を列挙する方法では、候補が非常に多くなり TLE になります。また、手紙をまとめて運べば疲労度が小さくなるようにも見えますが、疲労度は手紙の通数に比例するため、まとめても各手紙が生む疲労度は変わりません。ルートの組み合わせを考える必要はありません。

アルゴリズム

1. 地点 \(2\) から地点 \(N\) まで順番に見る。
2. 地点 \(i\) について、郵便局からの距離 \(i-1\) と手紙の通数 \(B_i\) を掛ける。
3. それらをすべて合計して出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: 補助領域は \(O(1)\)
  ただし、実装では入力全体を一度に読み込むため、入力バッファを含めると \(O(N)\)

実装のポイント

入力される最初の手紙の通数は地点 \(2\) の \(B_2\) です。その距離は \(1\) なので、enumerate(it, 1) によって距離を \(1\) から割り当てています。

また、答えは大きくなる可能性があります。Python の整数には固定長整数のようなオーバーフローがないため、そのまま計算できます。

ソースコード

import sys

it = map(int, sys.stdin.buffer.read().split())
next(it)
answer = sum(distance * letters for distance, letters in enumerate(it, 1))
print(answer)

---

この解説は gpt-5.6-sol-high によって生成されました。