概要

この問題は、与えられた \(N\) 曲のテンポ値 \(A_i\) を適切に並べ替えて、隣り合う曲や過去に再生した曲とのテンポ差によって生じる「違和感の総和」を最小化する問題です。

考察

この問題を解くための鍵は、テンポ値を数直線上の点として捉え、似ている曲同士をグループ（連結成分）に分けることです。

1. 「似ている」関係とグループ分け

テンポ値の差が \(D\) 以下である \(2\) 曲は「似ている」と定義されています。 テンポ値を昇順にソートした配列を \(A\) とします。隣り合う要素の差が \(D\) 以下である部分を線で結ぶと、いくつかのグループに分割できます。

例えば、 \(D = 2\)、テンポ値が \(A = [1, 3, 10, 11]\) の場合を考えてみましょう。 - \(1\) と \(3\) の差は \(2 \le D\) なので、同じグループになります。 - \(3\) と \(10\) の差は \(7 > D\) なので、異なるグループになります。 - \(10\) と \(11\) の差は \(1 \le D\) なので、同じグループになります。

結果として、\(\{1, 3\}\) と \(\{10, 11\}\) という \(2\) つのグループに分かれます。

2. グループ内での再生順

同じグループに属する曲同士は、テンポが昇順（または降順）に並ぶように連続して再生すれば、2曲目以降は常に「直前に再生した曲との差が \(D\) 以下」になります。 したがって、同じグループ内であれば、違和感スコアをすべて \(0\) に抑えて再生することが可能です。

3. グループ間の移動

問題は、異なるグループへ移動するとき（例：\(\{1, 3\}\) のグループから \(\{10, 11\}\) のグループへ移るとき）です。 新しいグループの最初の曲を再生する際、過去にその曲と「似ている（差が \(D\) 以下）」曲は再生されていないため、必ず違和感スコアが発生します。

このときの違和感スコアは「直前に再生した曲とのテンポ差」になります。 この差を最小にするには、直前のグループの最大値（右端）から、次のグループの最小値（左端）へ遷移するのが最適です。 上記の例で言えば、 \(3\) を再生した直後に \(10\) を再生するのが最もテンポ差が小さくなり、そのときの違和感スコアは \(10 - 3 = 7\) となります。

結論

すべての曲をテンポ値の昇順（ソートした順）に再生するのが最適です。 このとき、違和感スコアが発生するのは「ソートした配列において、隣り合う曲のテンポ差が \(D\) より大きい」境界のみになります。その境界での違和感スコアは、隣り合う曲のテンポ差そのもの（\(A_{i+1} - A_i\)）になります。

したがって、求める最小値は、ソート後の配列において 「隣り合う要素の差が \(D\) より大きい箇所の差の合計」 となります。

アルゴリズム

1. 与えられたテンポ値の配列 \(A\) を昇順にソートします。
2. 違和感の総和を保持する変数 ans を \(0\) で初期化します。
3. \(i = 0\) から \(N-2\) までループを回し、隣り合う要素の差 diff = A[i+1] - A[i] を計算します。
4. diff > D である場合、その diff を ans に加算します。
5. ループ終了後、 ans を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の要素のソートに \(O(N \log N)\) 時間かかります。その後のループ処理は \(O(N)\) なので、ソートがボトルネックとなります。 \(N \leq 10^6\) であるため、実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\)
  • 入力されたテンポ値を格納する配列 \(A\) のために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止: テンポ値 \(A_i\) は最大 \(10^9\) であり、違和感の総和（答え）は int 型（最大約 \(2 \times 10^9\)）の上限を超える可能性があります。そのため、答えを保持する変数やテンポ値を格納する配列には long long 型を使用します。

• 高速入出力: \(N\) が最大 \(10^6\) と非常に大きいため、C++では std::cin と std::cout の高速化（ios_base::sync_with_stdio(false); cin.tie(NULL);）を行うことで、実行時間を大幅に短縮できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // テンポ値を昇順にソート
    sort(A.begin(), A.end());

    long long ans = 0;
    // 隣り合うテンポ値の差が D より大きい場合、その差を違和感スコアとして加算する
    for (int i = 0; i < N - 1; ++i) {
        long long diff = A[i+1] - A[i];
        if (diff > D) {
            ans += diff;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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