概要

この問題は、一直線上に並ぶ各地点に手紙を届ける際の、最小の合計疲労度を求める問題です。一見すると「何回に分けて運ぶか」「どのタイミングで配るか」といった複雑な計画が必要に見えますが、手紙1通あたりが発生させる疲労度に着目すると、非常にシンプルな計算式で解くことができます。

考察

手紙1通に着目する

地点 \(j\)（\(2 \leq j \leq N\)）に届ける手紙を 1通だけ 運ぶことを考えてみましょう。 この手紙を地点 \(1\)（郵便局）から目的地である地点 \(j\) まで届けるためには、どうしても以下の区間をこの手紙を持った状態で通過しなければなりません。 - \(1 \to 2\)、 \(2 \to 3\)、 \(\ldots\)、 \(j-1 \to j\)

これらの区間を移動するとき、手元にこの手紙があるため、1区間進むごとに疲労度が \(1\) ずつ発生します。 地点 \(1\) から地点 \(j\) までの距離は \(j - 1\) なので、この手紙1通を届けるために発生する疲労度は、どのように運んでも最低 \(j - 1\) は必ず発生します。

無駄な動きをしない

もし、手紙を途中の地点まで運んでから一度郵便局に持ち帰り、次のルートで再び目的地へ運ぶ、といった無駄なことをすると、同じ区間をその手紙を持ったまま何度も通過することになり、発生する疲労度は \(j - 1\) よりも大きくなってしまいます。

したがって、すべての手紙について「1回だけ持ち出して、目的地に一直線に届ける」のが最も効率的です。

最小値の達成方法

すべての手紙を1回だけのルートで同時に持ち出し、地点 \(2, 3, \ldots, N\) と進みながら、それぞれの目的地で必要な通数だけ配っていくことを考えます。

このとき、どの手紙も「郵便局から出発して、目的地に到着するまで」の間だけ持ち運ばれるため、途中で持ち帰るなどの無駄が発生しません。 これにより、すべての手紙 \(j\) について、発生する疲労度を最小値である \(j - 1\) に抑えることができます。

したがって、求める疲労度の最小値は、各手紙が発生させる最小疲労度の総和となり、以下の式で表されます。

\[ \sum_{j=2}^{N} B_j \times (j - 1) \]

アルゴリズム

1. 地点 \(2\) から 地点 \(N\) までの手紙の数 \(B_2, B_3, \ldots, B_N\) を入力として受け取ります。
2. 各地点 \(j\) について、手紙の数 \(B_j\) に「郵便局からの距離 \(j - 1\)」を掛けた値を計算します。
3. それらの値をすべて足し合わせた総和を出力します。

計算量

• 時間計算量: \(O(N)\) 各地点の手紙の数に対して、1回ずつ掛け算と足し算を行うため、地点数 \(N\) に対する線形時間 \(O(N)\) で動作します。
• 空間計算量: \(O(N)\) 入力を配列（リスト）として保持するため、 \(O(N)\) のメモリを使用します。

実装のポイント

プログラム上でのインデックス（0から始まる番号）と、実際の地点番号（1から始まる番号）のズレに注意しましょう。

提供されたコードでは、B に \(B_2, B_3, \ldots, B_N\) が格納されています。 Pythonの enumerate(B) を使うと、ループ変数 i は \(0, 1, \ldots, N-2\) となります。 このとき、リストの i 番目の要素（b）は地点 \(j = i + 2\) 宛ての手紙の数に対応します。 この地点 \(j\) への距離は \(j - 1 = i + 1\) となるため、各ループで b * (i + 1) を計算して足し合わせることで、正しく答えを求めることができます。

ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    B = list(map(int, input_data[1:]))
    
    ans = sum(b * (i + 1) for i, b in enumerate(B))
    print(ans)

if __name__ == '__main__':
    main()

---

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