概要

一直線上に並んだ \(N\) 個の棚を、指定された開始位置からすべて1回ずつ検品するための合計時間の最小値を求める問題です。検品時間の合計は移動順序によらず一定であるため、移動時間の合計を最小化する経路を見つけることが鍵となります。

考察

まず、すべての棚をちょうど1回ずつ検品するため、検品時間の合計は移動する順序に関わらず常に \(\sum_{i=1}^{N} T_i\) となります。 したがって、この問題は「開始位置 \(S\) から出発し、すべての棚を1回ずつ訪れる際の移動距離の最小値を求める」という問題に帰着します。

棚は一直線上に並んでいるため、すべての棚を訪れるためには最終的に一番左の棚（棚 \(1\)）から一番右の棚（棚 \(N\)）までの全区間を移動しなければなりません。 開始位置 \(S\) が端っこ（棚 \(1\) または棚 \(N\)）であれば、もう一方の端まで一直線に移動するだけで済み、移動距離は \(N - 1\) となります。

しかし、開始位置 \(S\) が端ではない場合、どちらかの方向に進んだあと、折り返してもう一方の端まで進む必要があります。このとき、無駄な往復移動を最小限に抑えるには、以下の2パターンのいずれかを選ぶのが最適です。

1. 左端へ行ってから右端へ向かう場合: まず \(S\) から左端（棚 \(1\)）まで移動し、そこから右端（棚 \(N\)）まで移動します。 移動距離: \((S - 1) + (N - 1) = N + S - 2\)
2. 右端へ行ってから左端へ向かう場合: まず \(S\) から右端（棚 \(N\)）まで移動し、そこから左端（棚 \(1\)）まで移動します。 移動距離: \((N - S) + (N - 1) = 2N - S - 1\)

この2つのパターンのうち、移動距離が小さい方を選ぶことで移動時間を最小化できます。素朴な全探索（順列）を考えると \(O(N!)\) となり到底間に合いませんが、直線上の移動という性質を利用することで \(O(1)\) で最小移動距離を求めることができます。

アルゴリズム

1. 入力を受け取り、各棚の検品時間 \(T_i\) の合計 sum_T を計算します。
2. 左端へ先に向かう場合の移動距離 move1 = 2 * N - S - 1 を計算します。
3. 右端へ先に向かう場合の移動距離 move2 = N + S - 2 を計算します。
4. min_move = min(move1, move2) として最小の移動距離を求めます。
5. 最小移動距離に隣接移動時間 \(D\) を掛けたものと、検品時間の合計 sum_T を足したものが答えとなります。

計算量

• 時間計算量: \(O(N)\) （入力の読み込みと検品時間の総和の計算に \(O(N)\) かかります。経路探索は \(O(1)\) です。）
• 空間計算量: \(O(N)\) （入力を一度にリストとして保持するため。入力をストリームで読めば \(O(1)\) にもできます。）

実装のポイント

• 制約として \(N \leq 10^6\) と大きく、Pythonで標準入力を1行ずつ読み込む input() を使うと処理に時間がかかりTLE（実行時間超過）になる可能性があります。

• sys.stdin.buffer.read().split() を用いて入力を一度にすべてバイト列として読み込み、空白で分割することで、入力の読み込みを高速化しています。

• 計算過程で \(N, D, S, T_i\) が最大 \(10^9\) 程度になるため、答えが32ビット整数に収まらない場合があります。Pythonでは整数型のオーバーフローは自動的に処理されますが、C++等で実装する場合は64ビット整数（long long等）を用いる必要があります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    D = int(data[1])
    S = int(data[2])
    
    sum_T = sum(map(int, data[3:3+N]))
    
    move1 = 2 * N - S - 1
    move2 = N + S - 2
    
    min_move = move1 if move1 < move2 else move2
    
    ans = min_move * D + sum_T
    print(ans)

if __name__ == '__main__':
    main()

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