概要

一直線上に並んだ \(N\) 個の棚をすべて訪れて検品を行うとき、移動時間と検品時間の合計の最小値を求める問題です。

考察

1. 検品時間と移動時間の分離

この問題では「すべての棚をちょうど \(1\) 回ずつ検品する」必要があります。 棚 \(i\) を検品するのにかかる時間 \(T_i\) は、どのような順番で棚を回っても必ず発生します。 したがって、検品時間の総和 \(\sum_{i=1}^{N} T_i\) は常に一定であり、私たちが最小化すべきなのは移動時間の合計（＝移動距離の合計 \(\times D\)）だけです。

2. 移動距離の最小化

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

初期位置 \(S\) から出発して、左端 \(1\) と右端 \(N\) の両方を訪れるための移動経路は、本質的に以下の \(2\) パターンしかありません。

• パターンA：先に左端へ行き、折り返して右端へ行く
  • 経路： \(S \to 1 \to N\)
  • 移動距離： \((S - 1) + (N - 1)\)
• パターンB：先に右端へ行き、折り返して左端へ行く
  • 経路： \(S \to N \to 1\)
  • 移動距離： \((N - S) + (N - 1)\)

この \(2\) つの経路のうち、移動距離が短い方を選択するのが最適です。

3. 途中の棚の検品

「途中で通過しただけでは検品したことにならない」というルールがありますが、移動の途中でその棚に立ち止まって検品を行えば、余計な移動（往復）を一切増やすことなく、すべての棚をちょうど \(1\) 回ずつ検品できます。

例えば、初期位置 \(S\) から左端 \(1\) に向かう途中で、順に立ち止まって検品を行い、左端 \(1\) に到達した後は、右端 \(N\) に向かって移動しながら残りの棚（\(S\) より右側にある棚）を順に検品していけば、無駄な往復なしで全棚の検品が完了します。

したがって、最小の移動距離は以下のように表せます。 * \(N = 1\) のとき： \(0\) * \(N > 1\) のとき： \(\min(S - 1, N - S) + (N - 1)\)

アルゴリズム

1. 入力される検品時間 \(T_i\) の総和 sum_T を計算します。
2. 開始位置 \(S\) から左端までの距離 left_dist \(= S - 1\) と、右端までの距離 right_dist \(= N - S\) を計算します。
3. 最小移動距離 min_dist を \(\min(\text{left\_dist}, \text{right\_dist}) + (N - 1)\) として求めます（ただし \(N=1\) のときは \(0\)）。
4. 求める最小合計時間は sum_T + min_dist * D となります。

計算量

• 時間計算量: \(O(N)\) \(T_i\) の総和を計算するために入力を \(N\) 回走査する必要があります。その他の計算は \(O(1)\) で行えるため、全体として \(O(N)\) 時間で動作し、制限時間内に十分間に合います。
• 空間計算量: \(O(1)\) 入力された \(T_i\) はその場で累積和に加算すればよいため、配列などに保持する必要はありません。したがって、追加のメモリは定数極小量で済みます。

実装のポイント

• オーバーフローの防止: \(N, D, T_i\) の値が大きいため、合計時間は \(10^{18}\) 程度に達する可能性があります。C++では int 型（最大約 \(2 \times 10^9\)）ではなく、64ビット整数型である long long を使用して計算を行う必要があります。

• コーナーケースの考慮: \(N = 1\) の場合は移動が発生しないため、移動距離が \(0\) になるように処理を分岐させます。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    int S;
    if (!(cin >> N >> D >> S)) return 0;

    long long sum_T = 0;
    for (int i = 0; i < N; ++i) {
        long long t;
        cin >> t;
        sum_T += t;
    }

    long long min_dist = 0;
    if (N > 1) {
        long long left_dist = S - 1;
        long long right_dist = N - S;
        min_dist = min(left_dist, right_dist) + (N - 1);
    } else {
        min_dist = 0;
    }

    long long ans = sum_T + min_dist * D;
    cout << ans << "\n";

    return 0;
}

---

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