概要

一直線上に並んだ地点に手紙を届ける問題です。手紙を届けるために必要な全ルートの疲労度の合計の最小値を求めます。

考察

この問題を解くための重要な観察として、「1通の手紙が目的地に届くまでにかかる疲労度は、郵便局（地点1）から目的地までの距離に等しい」という点に気づくことが鍵となります。

例えば、地点 \(3\) 宛ての手紙を1通届ける場合を考えてみましょう。 地点1から出発し、地点2を経由して地点3に届けるためには、以下の2回の移動が伴います。 1. 地点1 \(\to\) 地点2 （このとき手元に手紙があるため、疲労度が \(1\) 発生） 2. 地点2 \(\to\) 地点3 （このとき手元に手紙があるため、疲労度が \(1\) 発生）

この手紙を1回のルートで届けようが、複数回のルートに分けて届けようが、地点1から地点3までの道のりを必ず運ばなければならないため、この手紙1通につき必ず \(2\) の疲労度が発生します。

この性質はすべての手紙に当てはまります。つまり、地点 \(i\)（\(2 \leq i \leq N\)）に届ける手紙は1通あたり \((i - 1)\) の疲労度を発生させます。

したがって、手紙をどのようにルートに分けたとしても、全ルートの疲労度の合計は不変であり、地点 \(i\) 宛ての手紙の通数 \(B_i\) に \((i - 1)\) を掛けたものの総和になります。これを最小化する（または最大化する）といった操作の余地はなく、そのまま足し合わせることで答えが求まります。

アルゴリズム

配列 \(B\) は地点 \(2\) から地点 \(N\) までの手紙の通数を表しています。 0-indexed の配列 B において、インデックス i の要素は地点 i + 2 の手紙の通数 \(B_{i+2}\) に対応します。 地点 i + 2 までの距離は (i + 2) - 1 = i + 1 であるため、疲労度の合計 ans に (i + 1) * B[i] を足し合わせていくことで答えを求めることができます。

具体的には、以下の計算を行います。 $\( \text{Ans} = \sum_{i=2}^{N} (i - 1) \times B_i \)$

計算量

• 時間計算量: \(O(N)\) 配列の要素を1回ずつ走査して足し合わせるだけなので、\(O(N)\) となります。\(N \leq 10^6\) であっても十分高速に処理できます。
• 空間計算量: \(O(N)\) 入力として受け取った配列 B を保存するために \(O(N)\) のメモリを必要とします。

実装のポイント

• 計算結果は非常に大きくなる可能性があるため、オーバーフローに注意する必要があります。Pythonでは整数型の桁数に制限がないため意識する必要はありませんが、C++等の言語では long long などの 64-bit 整数型を使用する必要があります。

• 入力が大きいため、Pythonでは sys.stdin.readline を使用して入力の読み込みを高速化すると安心です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    B = list(map(int, input().split()))
    ans = 0
    for i, b in enumerate(B):
        ans += (i + 1) * b
    print(ans)

if __name__ == '__main__':
    main()

---

この解説は or-glm5.2-high によって生成されました。