概要

\(N\) 曲をある順序で再生したときの「違和感の総和」を最小化する問題です。結論を言うと、テンポ値をソートして、隣り合う値の差が \(D\) より大きい箇所の差をすべて足し合わせるだけで答えが求まります。

考察

「似ている」関係でグループ分けする

まず、テンポ値を昇順にソートして考えます。ソートした列の中で「隣り合う値の差が \(D\) 以下」である曲同士は似ています。そこで、差が \(D\) より大きい箇所で列を区切ることで、曲を複数のグループ（クラスタ）に分けます。

例として \(A = [1, 3, 10, 12, 100]\)、\(D = 2\) を考えます。ソート済みで、隣の差は順に \(2, 7, 2, 88\) です。差が \(D=2\) より大きいのは \(7\) と \(88\) の箇所なので、

\[\{1, 3\} \mid \{10, 12\} \mid \{100\}\]

という \(3\) つのグループに分かれます。

ここで重要な性質があります： - 同じグループ内の曲は、隣同士の差が \(D\) 以下の鎖でつながっているので、うまく順番に再生すれば必ず「似ている曲が直前までに存在する」状態を作れます。 - 異なるグループの曲同士は、間に \(D\) より大きい隙間があるため、決して「似ている」とはみなされません。

ソート順に再生すると何が起こるか

ソートした順番（小さい方から）に再生してみましょう。

• グループ内では、直前の曲との差が \(D\) 以下なので、その曲は「似ている曲がすでに再生済み」となり、違和感スコアは \(0\)。
• グループの境界をまたぐ瞬間（差が \(D\) より大きい箇所）では、その曲は過去のどの曲とも差が \(D\) より大きい（過去の曲はすべて自分より小さく、最も近いのが直前の曲だから）ため、似ている曲が存在せず、違和感スコアは \(|B_j - B_{j-1}|\)、すなわちその差そのものになります。

先の例でソート順 \(1, 3, 10, 12, 100\) に再生すると： - \(1\)：1曲目なので \(0\) - \(3\)：\(|3-1|=2 \le 2\) なので似ている曲あり → \(0\) - \(10\)：直前 \(3\) との差 \(7 > 2\)、似ている曲なし → スコア \(7\) - \(12\)：\(|12-10|=2 \le 2\) → \(0\) - \(100\)：直前 \(12\) との差 \(88 > 2\) → スコア \(88\)

合計 \(7 + 88 = 95\)。これは「差が \(D\) より大きい箇所の差の総和」と一致します。

これが最小である理由

グループが \(m\) 個あるとき、各グループの「最初に再生される曲」は、それより前にそのグループの仲間が再生されていないため、必ず違和感スコアが発生します（全体の1曲目を除く）。つまり、\(m\) 個のグループを「つなぎ合わせる」コストが必ずかかります。

数直線上に並んだ \(m\) 個のグループを連結するための最小コストは、隣り合うグループ間の隙間（\(D\) より大きい差）をすべて足したものになります（数直線上の点を連結する最小全域木と同じ考え方で、離れたグループへ飛ぶと余計に距離がかかるため、隣のグループから入るのが最適です）。ソート順の再生はちょうどこの最小コストを達成しています。

素朴な方法ではなぜダメか

すべての再生順序を試すと \(N!\) 通りで、\(N \le 10^6\) では到底間に合いません。順序を直接探索するのではなく、上記の構造に気づくことで、ソート1回で答えが求まります。

アルゴリズム

1. テンポ値の配列 \(A\) を昇順にソートする。
2. 隣り合う要素の差 \(A_i - A_{i-1}\) を順に調べ、差が \(D\) より大きいときだけその差を答えに加算する。
3. 加算した合計が答え。

ソートして
ans = Σ (A[i] - A[i-1])   ただし (A[i] - A[i-1]) > D の項のみ

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（テンポ値を格納する配列）

実装のポイント

• オーバーフローに注意：差は最大 \(10^9\) 程度、項数は最大 \(10^6\) 個なので、合計は最大で \(10^{15}\) 規模になります。int では溢れるため、答えと差の計算は必ず 64bit 整数（long long）で行います。

• 「\(D\) 以下」と「\(D\) より大きい」の境界：似ているのは差が \(D\) 以下のときなので、加算するのは差が \(D\) を超える（diff > D）箇所だけです。等号の扱いを間違えないようにします。

• 高速入力：\(N \le 10^6\) と入力が大きいため、scanf や cin の速度に注意が必要です。サンプルコードでは fread による自前の高速読み込みを使っています（cin を使う場合は ios::sync_with_stdio(false) 等の高速化を入れると安心です）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

static char buf[1 << 25];
int bufLen = 0, bufPos = 0;

inline int readByte() {
    if (bufPos == bufLen) {
        bufLen = (int)fread(buf, 1, sizeof(buf), stdin);
        bufPos = 0;
        if (bufLen == 0) return -1;
    }
    return buf[bufPos++];
}

inline long long readLL() {
    int c = readByte();
    while (c != '-' && (c < '0' || c > '9')) {
        if (c == -1) return -1;
        c = readByte();
    }
    bool neg = false;
    if (c == '-') { neg = true; c = readByte(); }
    long long x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readByte();
    }
    return neg ? -x : x;
}

int main() {
    long long N = readLL();
    long long D = readLL();
    vector<int> a((size_t)N);
    for (long long i = 0; i < N; i++) {
        a[(size_t)i] = (int)readLL();
    }
    sort(a.begin(), a.end());
    long long ans = 0;
    for (long long i = 1; i < N; i++) {
        long long diff = (long long)a[(size_t)i] - (long long)a[(size_t)(i - 1)];
        if (diff > D) ans += diff;
    }
    printf("%lld\n", ans);
    return 0;
}

---

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