概要

すべての棚を検品する時間の合計は、検品順序によらず一定です。
したがって、最小化すべきなのは「移動時間」だけです。

考察

各棚 \(i\) の検品時間 \(T_i\) は、どの順番で検品しても必ずちょうど \(1\) 回ずつ加算されます。

そのため、検品時間の合計

\(T_1 + T_2 + \cdots + T_N\)

は固定です。

よって、この問題は次のように考えられます。

棚 \(S\) から出発して、棚 \(1\) から棚 \(N\) までをすべて訪れるために必要な最小移動距離を求める。

棚は一直線上に並んでいるため、すべての棚を検品するには、必ず左端の棚 \(1\) と右端の棚 \(N\) の両方を訪れる必要があります。

棚 \(S\) から出発して両端を訪れる方法は、大きく分けて次の \(2\) 通りです。

1. 先に棚 \(1\) に行き、その後棚 \(N\) まで行く
   移動距離は
   \((S - 1) + (N - 1)\)

2. 先に棚 \(N\) に行き、その後棚 \(1\) まで行く
   移動距離は
   \((N - S) + (N - 1)\)

どちらの場合も、棚 \(1\) から棚 \(N\) までの距離 \(N - 1\) は必ず移動する必要があります。
さらに、最初にどちらかの端まで行くための距離が必要です。

したがって、最小移動距離は

\((N - 1) + \min(S - 1, N - S)\)

となります。

例えば、\(N = 7, S = 3\) の場合を考えます。

• 左端に先に行く場合:
  棚 \(3 \to 1 \to 7\)
  移動距離は \(2 + 6 = 8\)

• 右端に先に行く場合:
  棚 \(3 \to 7 \to 1\)
  移動距離は \(4 + 6 = 10\)

よって、最小移動距離は \(8\) です。

隣接する棚の間の移動時間は \(D\) 分なので、移動時間は

\(\left((N - 1) + \min(S - 1, N - S)\right) \times D\)

です。

素朴に検品順序を全探索すると、順列をすべて試すことになり \(O(N!)\) となってしまい、\(N \leq 10^6\) では到底間に合いません。
しかし、検品時間は順序によらず固定であり、移動についても端点 \(1, N\) を訪れることだけ考えればよいので、簡単な式で求められます。

アルゴリズム

1. すべての検品時間の合計を求める。 $\( \text{total} = \sum_{i=1}^{N} T_i \)$

2. 最小移動距離を求める。 $\( \text{move\_steps} = (N - 1) + \min(S - 1, N - S) \)$

3. 移動時間を求める。 $\( \text{move\_time} = \text{move\_steps} \times D \)$

4. 答えは、検品時間の合計と移動時間の合計。 $\( \text{answer} = \text{total} + \text{move\_time} \)$

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

\(N\) は最大で \(10^6\) と大きいため、入力は sys.stdin.buffer.read() を使って高速に読み込んでいます。

また、答えは非常に大きくなる可能性があります。

• 検品時間の合計は最大で \(10^6 \times 10^9 = 10^{15}\)
• 移動時間も最大でおよそ \(10^6 \times 10^9 = 10^{15}\)

Python の整数型は多倍長整数なのでそのまま扱えますが、他の言語では 64 bit 整数型を使う必要があります。

ソースコード

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
N, D, S = data[0], data[1], data[2]
total_inspection = sum(data[3:])

move_steps = (N - 1) + min(S - 1, N - S)
ans = total_inspection + move_steps * D

print(ans)

---

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