概要

駐車場の外にある車を駐車可能エリア内に移動させるとき、必要な最小コストを求める問題です。

考察

この問題では、各車を独立に動かすことができ、コストは移動距離に等しいです。したがって、各車について、駐車可能エリア \([0, M]\) の外にいる場合に限り、最も近い駐車可能エリアの端（\(0\) または \(M\)）に移動するのが最適です。

例えば、ある車が座標 \(-5\) にあったとします。これは駐車場の左側にあり、座標 \(0\) まで移動するのが最短です。同様に、座標 \(M+3\) にある車は、座標 \(M\) まで移動すればよいです。

このように、各車は「自分より小さい値（負の座標）なら \(0\) へ」「\(M\) より大きい値なら \(M\) へ」移動するのが最適であり、それ以外の車はすでに駐車場内なので移動する必要はありません。

素朴な方法として、例えば車を一個ずつ動かしてみて最適な配置を探す、といったことを考えると計算量が膨大になりすぎるので、この問題では「各車の現在位置が範囲外かどうかだけを見て、その分だけコストを足す」というシンプルな方法で解けます。

アルゴリズム

1. 各車の座標 \(A_i\) を順番に確認する。
2. \(A_i < 0\) であれば、座標 \(0\) まで移動する必要があるため、コストに \(-A_i\) を加算する。
3. \(A_i > M\) であれば、座標 \(M\) まで移動する必要があるため、コストに \(A_i - M\) を加算する。
4. それ以外の場合はコストは増えない。
5. 最終的な合計コストを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力の配列を除く）

実装のポイント

• 各車の座標を一つずつ見て、範囲外の場合のみコストを計算する。

• 車の位置が負のときは \(0\) まで、\(M\) より大きいときは \(M\) まで移動させるという単純なロジックでOK。

• 特にソートや探索は不要なので、高速かつシンプルに処理できる。

  ソースコード

N, M = map(int, input().split())
A = list(map(int, input().split()))

total_cost = 0
for a in A:
    if a < 0:
        total_cost += -a
    elif a > M:
        total_cost += a - M

print(total_cost)

---

この解説は qwen3-coder-480b によって生成されました。