概要

この問題は、一直線上に並んだ \(N\) 個の棚をすべて訪問し、荷物の検品を終えるまでの最小合計時間を求める問題です。検品にかかる時間の総和はどのように移動しても変わらないため、実質的には開始位置 \(S\) からすべての棚を訪問するための最小移動距離を求める問題に帰着されます。

考察

1. 合計時間の分解

全体の作業時間は、「移動時間の合計」と「検品時間の合計」の2つに分けられます。 $\(\text{合計時間} = \text{移動時間の合計} + \text{検品時間の合計}\)$

ここで、すべての棚をちょうど1回ずつ検品する必要があるため、検品時間の合計は訪問する順番に関わらず、常に各棚の検品時間 \(T_i\) の総和となります。 $\(\text{検品時間の合計} = \sum_{i=1}^{N} T_i\)$ したがって、私たちは「移動時間の合計」を最小化することだけを考えればよいことになります。

2. 最小移動距離の考え方

棚は \(1\) から \(N\) まで一直線上に並んでいます。すべての棚を訪問するためには、必ず左端の棚 \(1\) と 右端の棚 \(N\) の両方を訪問しなければなりません。

開始位置 \(S\) から出発して、両端を含むすべての棚を訪問する最短の移動経路は、以下の2パターンのいずれかになります。

• パターンA（先に左端へ行く場合）

  1. 初期位置 \(S\) から、まず左端の棚 \(1\) まで一気に移動する。
  2. 棚 \(1\) で折り返し、右端の棚 \(N\) まで一気に移動する。
  • このときの移動距離は： $\((S - 1) + (N - 1)\)$

• パターンB（先に右端へ行く場合）

  1. 初期位置 \(S\) から、まず右端の棚 \(N\) まで一気に移動する。
  2. 棚 \(N\) で折り返し、左端の棚 \(1\) まで一気に移動する。
  • このときの移動距離は： $\((N - S) + (N - 1)\)$

途中にある他の棚（\(1\) と \(N\) の間にある棚）は、この往復移動の過程で必ずすべて通りかかります。通りかかる際に立ち止まって検品を行えば、追加の移動距離を発生させることなく、すべての棚の検品を完了させることができます。

したがって、最小移動距離はパターンAとパターンBの小さい方になります。 $\(\text{最小移動距離} = \min(S - 1, N - S) + (N - 1)\)$

具体例 (\(N = 5, S = 2\) の場合)

• パターンA（左端が先）: \(2 \to 1 \to 5\) と移動。
  • 距離は \(|2 - 1| + |1 - 5| = 1 + 4 = 5\)。
• パターンB（右端が先）: \(2 \to 5 \to 1\) と移動。
  • 距離は \(|2 - 5| + |5 - 1| = 3 + 4 = 7\)。
• 最小移動距離は \(\min(1, 3) + 4 = 5\) となり、パターンAが最適です。この移動の途中で、棚 \(3, 4\) も通過するため、そこで立ち止まって検品すれば追加の距離はかかりません。

アルゴリズム

1. 入力から \(N, D, S\) および各棚の検品時間 \(T_1, T_2, \ldots, T_N\) を読み込みます。
2. 検品時間の総和 \(\sum T_i\) を計算します。
3. 数式 \(\min(S - 1, N - S) \times D + (N - 1) \times D\) を用いて、最小移動時間を計算します。
4. 「最小移動時間」と「検品時間の総和」を足し合わせたものを答えとして出力します。

計算量

• 時間計算量: \(O(N)\) 検品時間 \(T_i\) の総和を計算する部分で \(O(N)\) の時間がかかります。移動時間の計算は \(O(1)\) で行えるため、全体の計算量は \(O(N)\) となり、 \(N \le 10^6\) でも十分高速に実行可能です。
• 空間計算量: \(O(N)\) 入力をリストとして保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonでは入力の要素数が多くなる（\(N = 10^6\) のとき \(T_i\) が \(10^6\) 個ある）ため、input() を繰り返すのではなく、sys.stdin.read().split() を用いて一括で入力を取得することで、実行時間を大幅に短縮できます。

• オーバーフローの心配: 答えは最大で \(10^{15}\) 程度の大きな値になりますが、Pythonは標準で多倍長整数（桁数制限のない整数）をサポートしているため、オーバーフローを気にする必要はありません。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    D = int(data[1])
    S = int(data[2])

    # T_i の合計を高速に計算
    sum_T = sum(map(int, data[3:]))

    # 1次元上のすべての点を訪問する最短移動距離は、
    # S -> 1 -> N の順（最後に右端Nに到達）か、
    # S -> N -> 1 の順（最後に左端1に到達）のいずれかになります。
    # したがって、最小移動距離は min(S - 1, N - S) * D + (N - 1) * D となります。
    min_move = min(S - 1, N - S) * D + (N - 1) * D

    ans = min_move + sum_T
    print(ans)


if __name__ == "__main__":
    solve()

---

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