概要

一直線上に並んだ \(N\) 個の棚を、開始位置 \(S\) からスタートしてすべて1回ずつ検品するときの、移動時間と検品時間の合計の最小値を求める問題です。

考察

まず、検品時間の合計はどの順序で検品を行っても必ず \(\sum_{i=1}^N T_i\) になります。したがって、この問題の本質は「移動時間の合計を最小化すること」です。

移動時間を最小化するための経路を考えます。棚は一直線上に並んでいるため、すべての棚を訪れるためには必ず左端の棚（棚 \(1\)）と右端の棚（棚 \(N\)）の両方に到達する必要があります。

開始位置 \(S\) からスタートしてすべての棚を1回ずつ訪れる最短経路は、以下の2パターンのいずれかになります。 1. 左端に行ってから右端に行くパターン: 棚 \(S\) から左端（棚 \(1\)）へ移動し、そこから右端（棚 \(N\)）まで移動して終了する。このときの移動距離は \((S - 1) + (N - 1)\) です。 2. 右端に行ってから左端に行くパターン: 棚 \(S\) から右端（棚 \(N\)）へ移動し、そこから左端（棚 \(1\)）まで移動して終了する。このときの移動距離は \((N - S) + (N - 1)\) です。

なぜこの2パターンだけで良いのかというと、移動中に通過した棚はそのまま検品できるため、途中で引き返すような無駄な移動をする必要がないからです。例えばパターン1の場合、\(S\) から \(1\) へ向かう途中の棚はすべて検品し、\(1\) から \(N\) へ向かう途中のまだ検品していない棚を検品していくことで、距離 \((S - 1) + (N - 1)\) で全ての棚を網羅できます。

素朴にすべての訪問順序を試すと \(N!\) 通りとなりTLEしますが、このように直線上の性質を利用することで移動距離の最小値は \(O(1)\) で求まります。

最後に、移動距離の最小値に \(D\) を掛けたものを検品時間の合計に足せば答えになります。なお、\(N, D, T_i\) が最大 \(10^9\) であるため、答えは最大で \(10^6 \times 10^9 \times 2 \approx 2 \times 10^{15}\) となり、32ビット整数型に収まらないことに注意が必要です。

アルゴリズム

1. 検品時間 \(T_i\) をすべて読み込み、その合計値 \(\text{sum\_T}\) を計算する。
2. 左端に行ってから右端に行く移動距離 \(\text{move1} = (S - 1) + (N - 1)\) を計算する。
3. 右端に行ってから左端に行く移動距離 \(\text{move2} = (N - S) + (N - 1)\) を計算する。
4. \(\text{move1}\) と \(\text{move2}\) の小さい方に \(D\) を掛け、最小移動時間 \(\text{min\_move}\) を求める。
5. 答え \(\text{sum\_T} + \text{min\_move}\) を出力する。

計算量

• 時間計算量: \(O(N)\) （\(T_i\) の入力と総和の計算に必要な時間）
• 空間計算量: \(O(1)\) （\(T_i\) を配列に保存せず順次足し合わせるため、定数領域しか使わない）

実装のポイント

• \(N, D, T_i\) が大きいため、計算途中および答えの格納に64ビット整数型（C++では long long）を使用する必要があります。

• \(T_i\) を配列に保持する必要はなく、入力を受け取るたびに合計値に足していくことでメモリ使用量を抑えることができます。

  ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, D, 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 move1 = S + N - 2;
    long long move2 = 2 * N - S - 1;
    long long min_move = min(move1, move2) * D;
    
    long long ans = sum_T + min_move;
    cout << ans << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。