概要

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

考察

気づき1: 検品時間は順序によらず固定

どの順序で検品しても、\(N\) 個すべての棚を検品するので、検品時間の合計は必ず \(\sum_{i=1}^{N} T_i\) になります。これは最適化の対象ではありません。したがって、移動時間をいかに小さくするかだけを考えればよいことが分かります。

気づき2: 両端の棚を必ず訪れる必要がある

すべての棚を検品しなければならないので、当然ながら一番左の棚 \(1\) と一番右の棚 \(N\) の両方を訪れる必要があります。

開始位置 \(S\) から見ると、 - 左端（棚 \(1\)）までの距離は \(\text{left} = S - 1\)（棚の個数換算） - 右端（棚 \(N\)）までの距離は \(\text{right} = N - S\)

の関係があります。

素朴なアプローチの問題点

「全順列を試す」ような全探索は \(N!\) 通りあり、\(N \leq 10^6\) では到底間に合いません。しかし、直線上の移動という構造を利用すれば、計算式だけで答えが求まります。

最適な移動の考え方

直線上で左端と右端の両方を訪れるとき、最も無駄のない動き方は次の2通りです。

1. まず左端へ行き、向きを変えて右端まで行く
   → 移動距離 \(= \text{left} + (N-1)\)
2. まず右端へ行き、向きを変えて左端まで行く
   → 移動距離 \(= \text{right} + (N-1)\)

どちらの場合も、一度どちらかの端まで行ってから区間全体（長さ \(N-1\)）を通り抜けるイメージです。途中の棚はその移動の最中に立ち寄って検品できるので、寄り道は発生しません。

この2つのうち小さい方を選べばよいので、最小移動距離（棚単位）は

\[ (N-1) + \min(\text{left}, \text{right}) \]

となります。最初に近い方の端へ向かう（\(\min\) を取る）のが得というわけです。

アルゴリズム

以下の手順で \(O(N)\) で答えが求まります。

1. 検品時間の合計 \(\text{sumT} = \sum T_i\) を計算する。
2. 左端までの距離 \(\text{left} = S-1\)、右端までの距離 \(\text{right} = N-S\) を求める。
3. 最小移動距離（棚単位）を \(\text{travel} = (N-1) + \min(\text{left}, \text{right})\) とする。
4. 答えは \(\text{sumT} + D \times \text{travel}\)。

具体例で確認してみましょう。\(N=5,\ S=2,\ D=10\) の場合、\(\text{left}=1,\ \text{right}=3\) なので、まず左端（棚1）へ行ってから右端（棚5）へ向かうのが得です。移動距離は \((5-1) + \min(1,3) = 4 + 1 = 5\) となり、移動時間は \(5 \times 10 = 50\) 分。これに検品時間の合計を足したものが答えです。

計算量

• 時間計算量: \(O(N)\)（入力を読みながら合計を取るだけ）
• 空間計算量: \(O(1)\)（各 \(T_i\) を保存する必要はなく、合計だけ保持すればよい）

実装のポイント

• オーバーフローに注意: \(T_i \leq 10^9\) が最大 \(10^6\) 個あるので合計は \(10^{15}\) 程度、さらに \(D \leq 10^9\) と移動距離（最大約 \(1.5 \times 10^6\)）の積も \(10^{15}\) 程度になります。これらの合計は 32bit 整数では収まらないため、必ず 64bit 整数型（C++ なら long long）を使います。

• 入力サイズが大きい: \(N\) が最大 \(10^6\) なので、高速な入力（C++ なら scanf など）を使うと安心です。

• \(T_i\) は合計に足し込むだけでよく、配列として全て保持する必要はないため、メモリ効率も良くなります。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; long long D; long long S;
    scanf("%d %lld %lld", &N, &D, &S);
    long long sumT = 0;
    for(int i=0;i<N;i++){
        long long t;
        scanf("%lld",&t);
        sumT += t;
    }
    long long left = S-1;
    long long right = (long long)N - S;
    long long travel = (long long)(N-1) + min(left, right);
    long long ans = sumT + D * travel;
    printf("%lld\n", ans);
    return 0;
}

---

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