概要

\(N\) 個のテンポ値を並べ替えて再生するとき、「直前まで似た曲がなかった場合に直前との差を払う」というルールで生じる違和感の総和を最小化する問題です。テンポ値をソートし、隣り合う値の差が \(D\) を超える箇所（ギャップ）の合計が答えになります。

考察

似ている曲を「グループ」として捉える

まず、テンポ値を昇順にソートして考えます。ソート後に隣り合う \(2\) つの値の差が \(D\) 以下なら、その \(2\) 曲は「似ている」と判定されます。

ここで重要な観察は、ソートした順に再生すれば、似ている曲どうしは数珠つなぎに連結できるということです。

例えば D = 2 で値が 1, 3, 10, 12 だったとします。ソート後の隣接差は - \(3 - 1 = 2\)（\(\leq D\)、似ている） - \(10 - 3 = 7\)（\(> D\)、似ていない） - \(12 - 10 = 2\)（\(\leq D\)、似ている）

となります。差が \(D\) 以下の部分でつながる曲をまとめると、\(\{1, 3\}\) と \(\{10, 12\}\) という \(2\) つの「グループ（クラスタ）」ができます。

グループ内のコストは 0 にできる

あるグループを小さい順に再生すると、\(2\) 曲目以降は必ず「直前の曲」と差が \(D\) 以下なので、似ている曲が過去に存在します。したがって違和感スコアは \(0\) です。

つまり、同じグループ内の曲はいくら再生しても追加コストがかからないのです。

コストが発生するのはグループをまたぐ瞬間だけ

グループをソート順に再生していくと、あるグループの最後（最大値）から次のグループの先頭（最小値）へ移るときだけコストが発生します。このときの差は、まさにソート上で「\(D\) を超えたギャップ」の値そのものです。

この移動先の曲は、それまでに再生したどの曲（すべて小さい側のグループに属する）とも差が \(D\) より大きいため、必ず違和感スコア \(|B_j - B_{j-1}|\) ＝ ギャップの値を支払います。

先ほどの例では、\(3 \to 10\) の移動で \(7\) を支払い、合計 \(7\) になります。

なぜこれが最小なのか

差が \(D\) を超えるギャップは、テンポ値の数直線を「越えられない壁」で区切るようなものです。すべての曲を再生する以上、各グループを少なくとも一度は「初めて再生」しなければならず、そのときは必ずどこか別のグループから飛んでくることになります。そのジャンプ幅は最小でも区切りのギャップ分だけ必要です。ソート順に再生する方法はこの下限ぴったりを達成するため、最適となります。

結論として、答えはソート後の隣接差のうち \(D\) を超えるものの総和です。

アルゴリズム

1. テンポ値の配列をソートする。
2. 隣り合う要素の差 diff = a[i] - a[i-1] を順に見る。
3. diff > D のとき、その diff を答えに加算する。
4. 合計を出力する。

なお \(N \leq 1\) のときはコストが発生しないので \(0\) を出力します。また \(D\) が大きくすべての差が \(D\) 以下なら答えは \(0\) になります。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)

実装のポイント

• \(N\) が最大 \(10^6\) と大きいため、入力の読み込みは高速化が必要です。sys.stdin.buffer.read() で一括読み込みしてから分割しています。

• 答えは最大で \(N \times 10^9\) 程度になり得ますが、Python の整数は多倍長なのでオーバーフローの心配はありません（C++ などでは long long を使う必要があります）。

• ソート後に隣接差を一度走査するだけなので、追加のデータ構造は不要です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    d = int(data[1])
    if n <= 1:
        print(0)
        return
    a = [int(x) for x in data[2:2 + n]]
    a.sort()
    ans = 0
    prev = a[0]
    for i in range(1, n):
        cur = a[i]
        diff = cur - prev
        if diff > d:
            ans += diff
        prev = cur
    print(ans)

main()

---

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