概要

\(N\) 個の希望日 \(D_i\) に対し、長さ \(K\) の区間 \([s, s+K-1]\) を適切に選んで、各 \(D_i\) と区間の距離（区間内なら 0）の合計を最小化する問題です。

考察

1. 不満度の正体

ある荷物の希望日が \(D_i\)、稼働期間が \([s, e]\)（ただし \(e = s + K - 1\)）のとき、その荷物の不満度を最小にするには、期間内の \(D_i\) に最も近い日に配達すればよいです。 - \(D_i < s\) のとき：\(s\) 日目に配達するのが最適で、不満度は \(s - D_i\) - \(s \le D_i \le e\) のとき：\(D_i\) 日目に配達できるので、不満度は \(0\) - \(D_i > e\) のとき：\(e\) 日目に配達するのが最適で、不満度は \(D_i - e\)

これらをまとめると、1つの荷物あたりの不満度は \(\max(0, s - D_i, D_i - e)\) と書けます。

2. 関数の性質と「中央値」の考え方

すべての荷物の不満度の合計を \(f(s)\) とすると、この関数は \(s\) に関する凸関数（下に凸なグラフ）になります。 \(f(s)\) の傾きがどう変化するかを考えます。\(s\) を \(1\) 増やしたとき： - \(D_i < s\) である荷物の不満度は \(1\) 増える - \(D_i > s + K - 1\) である荷物の不満度は \(1\) 減る - それ以外の荷物の不満度は変化しない

したがって、\(f(s)\) の傾きは 「(\(D_i < s\) となる荷物の数) - (\(D_i > s + K - 1\) となる荷物の数)」 となります。 この傾きが \(0\) になる場所が最小値の候補です。

ここで、条件を整理すると： - \(D_i < s\) \(\iff\) \(s > D_i\) - \(D_i > s + K - 1\) \(\iff\) \(s < D_i - K + 1\)

これらは、\(2N\) 個の値（\(D_i\) と \(D_i - K + 1\)）を並べたときの中央値付近で傾きが \(0\) になることを示唆しています。具体的には、これらの \(2N\) 個の値を昇順に並べた \(P_1, P_2, \ldots, P_{2N}\) のうち、\([P_N, P_{N+1}]\) の範囲の \(s\) で \(f(s)\) は最小になります。

3. 制約 \(s \ge 1\) の処理

問題文より \(s\) は正の整数である必要があるため、求めた中央値の範囲が \(1\) 未満になる場合は \(s=1\) とします。つまり、\(s = \max(1, P_N)\) とすれば、制約を満たしつつ \(f(s)\) を最小化できます。

アルゴリズム

1. 与えられた \(D_i\) をソートします。
2. \(2N\) 個の点 \(\{D_i\} \cup \{D_i - K + 1\}\) をすべてリスト \(P\) に入れ、ソートします。
3. \(s = \max(1, P_N)\) （\(0\)-indexed なら \(P[N-1]\)）を最適な開始日とします。
4. 終了日 \(e = s + K - 1\) を計算します。
5. 各荷物について、以下の合計を計算します（累積和や二分探索で高速化可能）：
   • \(D_i < s\) の場合：\((s - D_i)\)
   • \(D_i > e\) の場合：\((D_i - e)\)
   • それ以外：\(0\)

計算量

• 時間計算量: \(O(N \log N)\)
  • \(D_i\) のソートに \(O(N \log N)\) かかります。
  • \(2N\) 個の要素を持つ \(P\) のソートに \(O(N \log N)\) かかります。
  • 累積和の構築と二分探索（または走査）による不満度の計算は \(O(N)\) または \(O(\log N)\) です。
• 空間計算量: \(O(N)\)
  • 配列 \(D, P\) および累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な計算: \(N=2 \times 10^5\) と大きいため、不満度の合計を求める際は、毎回ループを回すのではなく、累積和を使って \(O(1)\) で範囲の合計を取得できるようにします。

• 中央値の選択: \(2N\) 個のデータの中央値は、ソート後の \(N\) 番目と \(N+1\) 番目の間の値ならどれでも最小値を与えます。コードでは \(P[N-1]\) を採用しています。

• \(K\) と \(D_i\) の大きさ: \(K\) や \(D_i\) は最大 \(10^9\) になるため、答えが 32bit 整数に収まらない可能性があります。Python では自動的に多倍長整数として扱われますが、他の言語では long long 等を使用する必要があります。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def solve():
    # 高速な入力を実現するためにsys.stdin.read().split()を使用
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 荷物の個数, K: 稼働期間の日数
    N = int(input_data[0])
    K = int(input_data[1])
    # D: 各荷物の希望配達日
    D = [int(x) for x in input_data[2:]]
    # 希望配達日を昇順にソート
    D.sort()
    
    # 稼働期間を [s, s + K - 1] としたとき、
    # 各荷物に対する最小不満度は max(0, s - Di, Di - (s + K - 1)) となる。
    # この不満度の合計を最小化する問題は、s に関する凸関数の最小値を求める問題であり、
    # その最小値は 2N 個の点 {Di} と {Di - K + 1} の中央値の範囲内で達成される。
    
    # 特徴点（不満度関数の傾きが変化する点）をすべてリストに加える
    P = D + [x - K + 1 for x in D]
    P.sort()
    
    # 2N 個の点の中央値の範囲は [P[N-1], P[N]] となる。
    # s は任意の正整数（s >= 1）である必要があるため、最適な s を以下のように選ぶ。
    # 中央値の範囲が 1 以上の整数を含むならそのいずれかを、
    # 範囲がすべて 1 未満なら s = 1 を選ぶことで、s >= 1 の範囲での最小値が得られる。
    s = max(1, P[N - 1])
    e = s + K - 1
    
    # 不満度の合計 f(s) を計算する。
    # f(s) = sum_{Di < s} (s - Di) + sum_{Di > s + K - 1} (Di - (s + K - 1))
    
    # 計算を高速化するために累積和を準備
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + D[i]
        
    # Di < s となる荷物の個数と合計
    idx_low = bisect_left(D, s)
    count_low = idx_low
    sum_low = prefix_sum[idx_low]
    cost_low = count_low * s - sum_low
    
    # Di > e となる荷物の個数と合計
    idx_high = bisect_right(D, e)
    count_high = N - idx_high
    sum_high = prefix_sum[N] - prefix_sum[idx_high]
    cost_high = sum_high - count_high * e
    
    # 最小の不満度合計を出力
    print(cost_low + cost_high)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。