概要

連続する \(K\) 日間の稼働期間を選び、全ての荷物を配達するときの不満度（希望日との差の絶対値）の合計を最小化する問題です。

考察

重要な気づき

1. 期間内の荷物は不満度0: 荷物の希望日 \(D_i\) が稼働期間 \([s, s+K-1]\) 内にあれば、希望日通りに配達できるので不満度は0です。

2. 期間外の荷物の最適な配達日:

   • 希望日 \(D_i < s\)（期間より前）の荷物 → 期間の初日 \(s\) に配達するのが最適 → 不満度は \(s - D_i\)
   • 希望日 \(D_i > s+K-1\)（期間より後）の荷物 → 期間の最終日 \(s+K-1\) に配達するのが最適 → 不満度は \(D_i - (s+K-1)\)

3. 開始日 \(s\) の候補の絞り込み: \(s\) は任意の正整数なので、全探索は不可能です（\(K \leq 10^9\)）。しかし、最適な \(s\) はある荷物の希望日が期間の端点になる場合に限られます。

なぜ候補が絞れるのか？

コスト関数を \(s\) の関数として考えると、区分的に線形な関数になります。傾きが変わるのは、ある荷物が「期間外」から「期間内」に切り替わる瞬間です。これは \(s = D_i\)（荷物 \(i\) が左端に来る）または \(s = D_i - K + 1\)（荷物 \(i\) が右端に来る）のときに起こります。

したがって、候補は高々 \(2N\) 個に絞られます。

アルゴリズム

1. 希望日 \(D\) をソートする
2. 全ての希望日が \(K\) 日間に収まる場合（\(D_{max} - D_{min} + 1 \leq K\)）、答えは0
3. 累積和 \(prefix[i] = D_0 + D_1 + \ldots + D_{i-1}\) を計算する
4. 候補となる \(s\) の値を列挙（各 \(D_i\) について \(s = D_i\) と \(s = D_i - K + 1\)）
5. 各候補 \(s\) に対してコストを計算し、最小値を求める

コストの計算方法（\(s\) を固定）

稼働期間を \([s, e]\)（\(e = s + K - 1\)）として：

• 左側のはみ出し: \(D_j < s\) となる荷物の不満度合計

  • 個数を \(L\)、和を \(S_L\) とすると、コストは \(L \cdot s - S_L\)

• 右側のはみ出し: \(D_j > e\) となる荷物の不満度合計

  • 個数を \(R\)、和を \(S_R\) とすると、コストは \(S_R - R \cdot e\)

二分探索と累積和を使えば、各候補に対して \(O(\log N)\) で計算できます。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソート: \(O(N \log N)\)
  • 累積和の構築: \(O(N)\)
  • 各候補（高々 \(2N\) 個）に対するコスト計算: \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • ソート後の配列と累積和の保持

実装のポイント

1. 二分探索の使い分け:

   • bisect_left(D, s): \(D_j < s\) となる要素数（\(s\) 未満の個数）
   • bisect_right(D, e): \(D_j \leq e\) となる要素数（\(e\) より大きい要素の開始位置）

2. 累積和の活用: 範囲内の和を \(O(1)\) で求めるため、事前に累積和を計算しておく

3. 候補の重複排除: set を使って候補を管理することで、同じ \(s\) を複数回計算することを防ぐ

4. 特殊ケースの処理: 全ての荷物が \(K\) 日間に収まる場合は、早期に0を出力して終了

   ソースコード

import sys
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = [int(input_data[i + 2]) for i in range(N)]
    
    D.sort()
    
    # 全ての荷物が K 日間に収まる場合
    if D[-1] - D[0] + 1 <= K:
        print(0)
        return
    
    # 累積和を計算
    # prefix[i] = D[0] + D[1] + ... + D[i-1]
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + D[i]
    
    # 稼働期間を [s, s+K-1] とする
    # 荷物 i の希望日 D[i] が期間内なら不満度 0
    # D[i] < s なら、配達日は s にするのが最適 → 不満度 s - D[i]
    # D[i] > s+K-1 なら、配達日は s+K-1 にするのが最適 → 不満度 D[i] - (s+K-1)
    
    # 最適な s の候補は、ある荷物の希望日が期間の左端または右端になるケース
    # つまり s = D[i] または s = D[i] - K + 1 の形
    
    # s を固定したとき、
    # - D[j] < s となる荷物: 不満度の合計 = (個数) * s - (それらの D[j] の和)
    # - D[j] > s + K - 1 となる荷物: 不満度の合計 = (それらの D[j] の和) - (個数) * (s + K - 1)
    
    def calc_cost(s):
        # 稼働期間 [s, s + K - 1]
        e = s + K - 1
        
        # D[j] < s となる個数と和
        left_count = bisect_left(D, s)
        left_sum = prefix[left_count]
        
        # D[j] > e となる個数と和
        right_idx = bisect_right(D, e)
        right_count = N - right_idx
        right_sum = prefix[N] - prefix[right_idx]
        
        cost = left_count * s - left_sum + right_sum - right_count * e
        return cost
    
    min_cost = float('inf')
    
    # 候補となる s の値を列挙
    candidates = set()
    for d in D:
        candidates.add(d)  # s = d (d が期間の左端)
        candidates.add(d - K + 1)  # s = d - K + 1 (d が期間の右端)
    
    for s in candidates:
        cost = calc_cost(s)
        min_cost = min(min_cost, cost)
    
    print(min_cost)

solve()

---

この解説は claude4.5opus によって生成されました。