概要

一直線上に並んだ \(N\) 個の棚すべてを検品するときの「移動時間＋検品時間」の合計の最小値を求める問題です。検品時間の合計は固定なので、実質的には移動時間を最小化する問題になります。

考察

検品時間は固定である

まず重要な気づきとして、すべての棚をちょうど1回ずつ検品するため、検品時間の合計 \(\sum_{i=1}^{N} T_i\) は検品の順序によらず常に一定です。したがって、最小化すべきなのは移動時間だけだとわかります。

移動時間の最小化＝直線上の全点訪問問題

棚は一直線上に番号順に並んでいるため、これは「数直線上の点 \(S\) から出発して、\(1\) から \(N\) までのすべての点を訪問する最短経路」を求める問題に帰着します。

すべての棚を訪問するには、必ず左端の棚 \(1\) と右端の棚 \(N\) の両方を訪れる必要があります。一度この両端をカバーすれば、その途中にある棚はすべて通過済みになります（ただし通過だけでは検品にならないので、移動の経路上で立ち止まって検品すればよいだけです）。

最適な移動の仕方

出発点 \(S\) から両端 \(1\) と \(N\) を訪れる方法は、本質的に次の2通りです。

1. 先に左端 \(1\) へ行き、その後右端 \(N\) へ向かう
   • 移動距離（棚の数）: \((S-1) + (N-1)\)
2. 先に右端 \(N\) へ行き、その後左端 \(1\) へ向かう
   • 移動距離（棚の数）: \((N-S) + (N-1)\)

どちらも全体の幅 \((N-1)\) を1回はフルに横切り、それに加えて「近い側の端までの距離」を1回だけ余分に往復します。

したがって最小移動距離（棚単位）は次のようになります。

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

ここで \(S-1\) は左側にある棚の数、\(N-S\) は右側にある棚の数です。近い方の端を先に処理するのが得というわけです。

具体例

\(N=5,\ S=3\) の場合を考えます。左側に \(S-1=2\) 個、右側に \(N-S=2\) 個の棚があります。 - 左端 \(1\) へ先に行く場合: \(3 \to 1\)（距離2）→ \(1 \to 5\)（距離4）= 合計6 - 右端 \(5\) へ先に行く場合: \(3 \to 5\)（距離2）→ \(5 \to 1\)（距離4）= 合計6

公式では \((5-1) + \min(2,2) = 4 + 2 = 6\) となり一致します。

最終的な答えは、この移動距離に \(D\) を掛けたものに検品時間の合計を加えた値です。

\[ \text{答え} = \sum_{i=1}^{N} T_i + D \times \left( (N-1) + \min(S-1,\ N-S) \right) \]

アルゴリズム

1. 検品時間の合計 \(\text{total} = \sum_{i=1}^{N} T_i\) を計算する。
2. \(N = 1\) のときは移動が不要なので、答えは \(\text{total}\) のみ。
3. それ以外は、左側の棚数 \(S-1\) と右側の棚数 \(N-S\) の小さい方を選び、移動距離を \((N-1) + \min(S-1, N-S)\) とする。
4. \(\text{total} + D \times (\text{移動距離})\) を出力する。

特別な探索や動的計画法は不要で、閉じた式（公式）で直接計算できるのがこの問題のポイントです。

計算量

• 時間計算量: \(O(N)\) （検品時間の合計を求める入力読み込み部分が支配的）
• 空間計算量: \(O(N)\) （入力データの保持。実際には逐次読みで \(O(1)\) にもできる）

実装のポイント

• 入力サイズが大きい（\(N \leq 10^6\)）ため、Python では sys.stdin.buffer.read() を使って一括で読み込み、高速に処理しています。1行ずつ input() で読むと遅くなる可能性があります。

• \(T_i\) や \(D\) が最大 \(10^9\) で \(N\) も大きいため、合計値は非常に大きくなりますが、Python の整数は多倍長で自動的に扱えるためオーバーフローの心配はありません（C++ などでは long long 以上が必要になる点に注意）。

• \(N = 1\) のときに \(\min(S-1, N-S)\) や \((N-1)\) が \(0\) となるよう、場合分け不要に見えますが、コードでは明示的に分岐して安全に処理しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); d = int(data[1]); s = int(data[2])
    total = 0
    for i in range(n):
        total += int(data[3 + i])
    if n == 1:
        print(total)
        return
    left = s - 1
    right = n - s
    travel = (n - 1) + min(left, right)
    print(total + d * travel)

main()

---

この解説は claude4.8opus-high によって生成されました。