概要

すべての棚をちょうど \(1\) 回ずつ検品するための最小合計時間を求めます。
検品時間の合計は順序によらず一定なので、最小化すべきなのは「移動時間」だけです。

考察

まず、各棚の検品時間 \(T_i\) は、すべての棚を必ず \(1\) 回ずつ検品するため、どの順番で回っても合計は常に

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

で一定です。

したがって、この問題は次のように言い換えられます。

棚 \(S\) から出発して、棚 \(1\) から棚 \(N\) までをすべて訪れるときの最小移動距離を求める。

棚は一直線上に並んでいるため、すべての棚を訪れるには、最終的に区間 \([1, N]\) 全体をカバーする必要があります。

棚 \(1\) から棚 \(N\) までの距離は

\((N - 1) \times D\)

です。

開始位置が棚 \(S\) の場合、すべての棚を訪れる最短ルートは次のどちらかです。

1. 先に棚 \(1\) 側へ行き、その後棚 \(N\) まで進む
2. 先に棚 \(N\) 側へ行き、その後棚 \(1\) まで進む

それぞれの移動距離は以下の通りです。

• 棚 \(1\) に先に行く場合
  \((S - 1) + (N - 1)\) 棚分の移動
• 棚 \(N\) に先に行く場合
  \((N - S) + (N - 1)\) 棚分の移動

よって、最小移動距離は

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

です。

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

• 棚 \(1\) に先に行く: \(2 \to 1 \to 5\)
  移動棚数は \(1 + 4 = 5\)
• 棚 \(5\) に先に行く: \(2 \to 5 \to 1\)
  移動棚数は \(3 + 4 = 7\)

したがって、最小移動棚数は \(5\) です。

素朴に検品順序を全探索すると、順列は \(N!\) 通りあり、\(N \leq 10^6\) では到底間に合いません。
しかし、一直線上の棚をすべて訪れる場合、端から端までの移動が必須であることに注目すると、上の式だけで求められます。

アルゴリズム

1. \(T_i\) をすべて読み込み、検品時間の合計 total を求める。
2. 最小移動時間を次の式で求める。

\(move = ((N - 1) + \min(S - 1, N - S)) \times D\)

1. 答えは

\(total + move\)

である。

計算量

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

実装のポイント

\(N, D, T_i\) は大きく、合計時間は \(10^{15}\) 程度になる可能性があります。
そのため、int ではなく long long を使う必要があります。

また、\(T_i\) は合計だけが必要なので、配列に保存する必要はありません。読み込みながら total に足していけば十分です。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, D, S;
    cin >> N >> D >> S;

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

    long long move = ((N - 1) + min(S - 1, N - S)) * D;
    cout << total + move << '\n';

    return 0;
}

---

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