概要

\(N\) 個の荷物の希望配達日が与えられ、連続する \(K\) 日間の稼働期間内で全てを配達するとき、不満度の合計を最小化する問題。

考察

各荷物を配送する日を連続する \(K\) 日間の中から自由に選べるため、最適な区間 \([s, s+K-1]\) を選ぶことが重要です。
\(i\) 番目の荷物を日付 \(x\) に配達したときの不満度は \(|D_i - x|\) であり、これは区間 \([s, s+K-1]\) 内での最適な \(x\) は \(D_i\) をその区間に「クリップ」した値、すなわち \(\max(s, \min(D_i, s+K-1))\) となります。

したがって、ある区間 \([s, s+K-1]\) における全体の不満度の合計は以下のように計算できます： $\( \sum_{i=1}^{N} \max(s - D_i, 0) + \max(D_i - (s+K-1), 0) \)$

これは、\(D_i < s\) ならば \(s - D_i\)、\(D_i > s+K-1\) ならば \(D_i - (s+K-1)\) のコストが発生し、それ以外はコスト 0 です。

単純に \(s\) を全探索すると、\(D_i\) の値が最大で \(10^9\) なので計算量が膨大になりTLEになります。
そこで、\(D\) をソートしておき、区間の左端 \(s\) に関するコスト関数が凸関数であることに注目し、三分探索を用いて最小値を求めます。

さらに、各区間に対するコスト計算を高速に行うために、累積和を使い、\(s\) より小さい/大きい要素の個数と合計を高速に求めています。

アルゴリズム

1. 入力を読み込み、荷物の希望配達日リスト \(D\) を昇順にソートします。
2. 累積和を事前に計算しておきます。
3. 区間の左端 \(s\) の候補を三分探索で絞り込みます。
4. 各 \(s\) に対して、対応する右端 \(s+K-1\) を求め、全体のコストを計算します：
   • \(D_i < s\) である要素の数 \(l\_cnt\) とその合計 \(l\_sum\) を二分探索で取得
   • \(D_i > s+K-1\) である要素の数 \(r\_cnt\) とその合計 \(r\_sum\) を同様に取得
   • コストは： $\( l\_cnt \cdot s - l\_sum + r\_sum - r\_cnt \cdot (s+K-1) \)$
5. 探索範囲を狭めた後、最終的に候補となる \(s\) 近傍で正確な最小値を求めます。

計算量

• 時間計算量: \(O(N \log N + T)\) （\(T\) は三分探索と最終候補の計算にかかる時間。実質 \(O(N \log N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• \(D\) は必ずソートしておく必要があります。
• 累積和を使うことで、区間の和を高速に求められます。
• 二分探索 (bisect) を使って、区間内外の要素数・和を高速に求めます。
• 三分探索では、区間を3分割してコストが小さくなる方へ探索範囲を狭めていきます。
• 最終的には探索範囲の周辺で実際にコストを計算して最小値を確定させます。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    D = list(map(int, data[2:]))
    
    D.sort()
    
    # 累積和を計算
    acc = [0] + list(accumulate(D))
    
    min_cost = float('inf')
    
    # 稼働開始日 s を全探索 (最大で D_max - K + 1 まで)
    # しかし N,K,D_i が大きいため、効率的な方法が必要
    
    # 最適な連続区間 [left, left + K - 1] を見つける
    # 各荷物 i の最適な配達日は max(left, min(D[i], left + K - 1)) = median的な考え方ではない
    # 実際には、連続K日の中で、コスト |D[i] - x| の総和を最小にするxの範囲は中央値付近
    
    # よって、連続するK日の区間をスライドさせて、各区間における最小コストを高速に求めたい
    # 区間 [L, R] 内で、各 D[i] をある日 x に寄せたときのコスト総和の最小値を知りたい
    # 最適な x は D のうち区間に含まれる要素の中央値（の一つ）
    
    # スライディングウィンドウ的に、Dの連続部分列の長さKの区間を考えるわけではない
    # あくまで、稼働日が連続K日、荷物はその中に自由に割り当て可能
    
    # 考え方：
    # 稼働日を [s, s+K-1] とする。
    # 各D[i]について、最適な配達日x_i ∈ [s, s+K-1] を選ぶ。
    # 最適なx_iは、max(s, min(D[i], s+K-1)) つまり、D[i]を[s,s+K-1]内にクリップしたもの
    
    # つまり、コストは Σ_i |D[i] - clip(D[i], s, s+K-1)|
    # この関数は凸関数なので、三分探索などで最小値を求められるが、ここでは別のアプローチ
    
    # 別解：Dをソートしておき、連続するK個の要素を区間として選び、それに対応する最適な[s,s+K-1]を決める
    
    # 最も良いのは、Dの中央値近辺をカバーするような区間を選ぶこと
    
    # 方法：
    # Dをソート済みとする。
    # すべての荷物を[s, s+K-1]内で配達するときの最小コストは：
    # Σ_i max(0, |D[i] - clip(D[i], s, s+K-1)|) → 実際にはΣ|min(max(D[i], s), s+K-1) - D[i]|
    
    # 効率的な計算：
    # Dをソートしておく。
    # 稼働区間[s, s+K-1]に対して、Dの中でs未満のものはsに、s+K-1より大きいものはs+K-1に割り当てるのが最適
    # 残りはそのままD[i]に割り当てられる（=不満0）
    
    # よって、Dの中で < s であるものの数をl_cnt, 和をl_sum
    # Dの中で > s+K-1 であるものの数をr_cnt, 和をr_sum
    # とすれば、
    # コスト = l_cnt * s - l_sum + r_sum - r_cnt * (s+K-1)
    
    # これを効率的に計算するために、Dをソートし、sの候補を絞る
    
    # s の候補としては、D[i] または D[i]-K+1 などが候補になる
    
    # だが、もっと良いのは、Dの要素を使って稼働区間を決定すること
    
    # 解法：
    # Dをソートしておく。
    # 稼働区間の左端を L、右端を R = L + K - 1 とする。
    # すべてのD[i]を[L,R]内の日付に移動させる。
    # コストは Σ_i max(L - D[i], 0) + max(D[i] - R, 0)
    
    # つまり、D[i] < L ならコスト L - D[i]
    #       D[i] > R ならコスト D[i] - R
    #       L <= D[i] <= R ならコスト 0
    
    # これを最小化するL,R (R - L + 1 = K) を探す
    
    # Dをソート済みとする
    # Lの候補は D[0] - K + 1 から D[N-1] まで考えられるが、それは無限大
    
    # 実際には、最適なLは D の要素でも、それより前後してもよい？
    # しかし、最適な区間[L,R]は少なくとも1つのD[i]を含むべき
    
    # よって、Lの候補として、D[i] - K + 1 〜 D[i] などを考えても良い
    
    # ここでは、効率的に計算するために、「何番目の荷物までがL未満か」を二分探索で求める
    
    def compute_cost(L):
        R = L + K - 1
        # D[i] < L の個数と和
        from bisect import bisect_left, bisect_right
        idx_L = bisect_left(D, L)
        idx_R_plus1 = bisect_right(D, R)
        
        l_cnt = idx_L
        r_cnt = N - idx_R_plus1
        
        l_sum = acc[l_cnt]
        r_sum = acc[N] - acc[idx_R_plus1]
        
        cost = l_cnt * L - l_sum + r_sum - r_cnt * R
        return cost
    
    # Lの候補を全探索するには多すぎるので、三分探索を行う
    left = min(D) - K
    right = max(D) + 1
    
    for _ in range(100):  # 十分な反復回数
        c1 = left + (right - left) // 3
        c2 = right - (right - left) // 3
        if compute_cost(c1) > compute_cost(c2):
            left = c1
        else:
            right = c2
            
    # 最後に、left周辺のいくつかの整数値で最小値を確認
    res = float('inf')
    for l in range(left - 2, left + 3):
        res = min(res, compute_cost(l))
        
    print(res)

if __name__ == "__main__":
    main()

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