概要

各車の位置 \(A_i\) を区間 \([0, M]\) に収めるために、必要な移動距離（コスト）の合計の最小値を求めます。

考察

この問題の重要な点は、「車同士に制約がない」ことです。つまり、

• ある車をどこに動かしても、他の車の移動に影響しない
  
• 移動後に同じ座標に複数台いてもよい
  

したがって、全体の最小コストは 各車について最小コストで区間 \([0,M]\) に入れる ことを \(N\) 台分足し合わせたものになります。

では、1台の車が座標 \(x\) にいるとき、最小コストはどうなるでしょうか。

• \(0 \le x \le M\) のとき：すでに範囲内なので動かす必要がなく、コストは \(0\)
• \(x < 0\) のとき：最も近い範囲内の点は \(0\) なので、\(0\) に動かすのが最小
  コストは \(|x-0| = -x\)
• \(x > M\) のとき：最も近い範囲内の点は \(M\) なので、\(M\) に動かすのが最小
  コストは \(|x-M| = x-M\)

素朴に「どこへ移動させるか」を探索したり、全車をまとめて最適化しようとすると不要に複雑になりますが、本問題は独立性のおかげで 各車の“はみ出し量”だけを足せばよい という単純な形に落ちます。

具体例：\(M=10\) のとき - \(x=-3\) → \(0\) に寄せる（コスト \(3\)） - \(x=5\) → そのまま（コスト \(0\)） - \(x=13\) → \(10\) に寄せる（コスト \(3\)）

合計 \(3+0+3=6\) が最小です。

アルゴリズム

1. 合計コスト ans = 0 を用意する
2. 各 \(A_i\) について以下を行う
   
   • もし \(A_i < 0\) なら ans += -A_i（\(0\) まで戻す距離）
   • もし \(A_i > M\) なら ans += A_i - M（\(M\) まで戻す距離）
   • それ以外（\(0 \le A_i \le M\)）は加算しない
3. ans を出力する

これは「区間への射影（クリップ）」を各点に対して行い、その移動距離を足しているのと同じです。

計算量

• 時間計算量: \(O(N)\)（各車を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（入力以外に定数個の変数のみ）

実装のポイント

• \(N\) が最大 \(2\times 10^5\) なので、Python では sys.stdin.buffer.read() を使うと高速に入力できます。

• 合計コストは最大で \(N \times 10^9\) 程度になり得ますが、Python の int は多倍長なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    A = data[2:2+N]

    ans = 0
    for x in A:
        if x < 0:
            ans += -x
        elif x > M:
            ans += x - M
    print(ans)

if __name__ == "__main__":
    main()

---

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