概要

長さ \(K\) の連続区間 \([L,\,R]\)（\(R=L+K-1\)）を選び、各荷物はその区間内で最も不満度が小さくなる日に配達するとして、合計不満度 \(\sum |D_i-x_i|\) の最小値を求めます。

考察

1. 区間が決まれば各荷物の最適配達日は一意に決まる

稼働区間を \([L, R]\) とすると、希望日が \(D_i\) の荷物は - \(D_i < L\) なら \(L\) に配達（不満度 \(L-D_i\)） - \(L \le D_i \le R\) なら \(D_i\) に配達（不満度 \(0\)） - \(D_i > R\) なら \(R\) に配達（不満度 \(D_i-R\)）

つまり不満度は [ \max(0,\,L-D_i) + \max(0,\,D_i-R) ] となり、区間を選ぶ問題に帰着します。

2. 素朴解が間に合わない理由

\(L\) は最大 \(10^9\) まで取り得るため、全ての \(L\) を試すのは不可能です。また、各 \(L\) ごとに \(N\) 個を愚直に計算すると \(O(N\cdot 10^9)\) で論外です。

3. 「値が変わる点」だけ調べればよい（区分的線形）

合計不満度 [ F(L)=\sum_i \bigl(\max(0,\,L-D_i) + \max(0,\,D_i-(L+K-1))\bigr) ] は、\(L\) に関して区分的に一次関数になります。形が変わる（傾きが変わる）のは以下のような境界を跨ぐときです：

• ある \(D_i\) が「\(D_i < L\)」側に入る瞬間：\(L = D_i\) 付近
  
• ある \(D_i\) が「\(D_i > R\)」側から外れる瞬間：\(D_i = R\) すなわち \(L = D_i - (K-1)\) 付近（整数なので \(D_i-K\) や \(D_i-K+1\) が重要）

よって最小値は、これら境界の近く（整数の切れ目）にある候補 \(L\) を列挙して評価すれば十分です。コードでは候補として - \(D_i,\ D_i+1\) - \(D_i-K,\ D_i-K+1\) - そして制約 \(L\ge 1\) のため \(1\) を集めて重複除去し、それらだけを全探索しています。

（例）\(K=3\) のとき \(R=L+2\)。ある荷物の \(D=10\) が「右側はみ出し」になる条件は \(10>R\)、つまり \(L\le 7\)。この境目は \(L=8\)（=\(10-K+1\)）なので、\(10-K\) と \(10-K+1\) の周りを見れば十分、という感覚です。

アルゴリズム

1. 希望日配列 \(D\) を昇順ソートする。
2. 累積和 pre を作る（pre[t]=D[0]+...+D[t-1]）。
3. 候補となる開始日 \(L\) を以下で列挙し、\(1\) 未満は \(1\) に丸め、ソートして重複除去する：
   • \(1\)
   • 各 \(d\in D\) について \(d,\ d+1,\ d-K,\ d-K+1\)
4. 各候補 \(L\) について \(R=L+K-1\) とし、二分探索で
   • \(i=\#\{D_i < L\}\)（bisect_left）
   • \(j=\#\{D_i \le R\}\)（bisect_right） を求める。
5. 合計不満度を高速に計算する：
   • 左側（\(D_i<L\)）の和
     [ \sum_{t< i}(L-D_t)=L\cdot i-\text{pre}[i] ]
   • 右側（\(D_i>R\)）の和
     [ \sum_{t\ge j}(D_t-R)=(\text{pre}[N]-\text{pre}[j]) - R\cdot (N-j) ]
   • 合計 left + right を最小化する。
6. 最小値を出力する。

計算量

• 時間計算量: ソート \(O(N\log N)\) ＋ 候補数 \(O(N)\) 個それぞれ二分探索 \(O(\log N)\) なので全体で \(O(N\log N)\)
• 空間計算量: ソート済み配列・累積和・候補配列で \(O(N)\)

実装のポイント

• 不満度計算は \(D\) をソートし、累積和で区間外の寄与をまとめて計算すると \(O(\log N)\) で済みます。

• \(L\) は必ず正整数なので、候補生成時に \(1\) 未満は \(1\) に丸めています。

• 候補点は重複が多いので、ソートしてから一度走査して重複除去すると効率的です。

• 合計は最大で大きくなり得るため（\(N\le 2\times 10^5,\ D_i\le 10^9\)）、64bit相当の整数が必要ですが、Python の int なら安全です。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    D = [next(it) for _ in range(N)]
    D.sort()

    pre = [0] * (N + 1)
    s = 0
    for i, x in enumerate(D, 1):
        s += x
        pre[i] = s
    preN = pre[N]

    cands = [1]
    for d in D:
        a = d
        b = d + 1
        c = d - K
        e = d - K + 1
        if a < 1: a = 1
        if b < 1: b = 1
        if c < 1: c = 1
        if e < 1: e = 1
        cands.append(a)
        cands.append(b)
        cands.append(c)
        cands.append(e)

    cands.sort()
    uniq = []
    prev = None
    for x in cands:
        if x != prev:
            uniq.append(x)
            prev = x

    INF = 10**30
    ans = INF
    km1 = K - 1

    for L in uniq:
        R = L + km1
        i = bisect_left(D, L)
        j = bisect_right(D, R)

        left = L * i - pre[i]
        right = (preN - pre[j]) - R * (N - j)
        total = left + right
        if total < ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

---

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