概要

テンポ値を好きな順番に並べたとき、過去に似た曲がなければ発生する違和感スコアの総和を最小化する問題です。

結論として、テンポ値を昇順にソートし、隣り合う値の差が \(D\) より大きいところだけを足し合わせれば答えになります。

考察

まず、テンポ値を昇順に並べたものを

\(A_1 \leq A_2 \leq \cdots \leq A_N\)

とします。

隣り合うテンポ値の差 \(A_i - A_{i-1}\) に注目します。

差が \(D\) 以下の場合

\(A_i - A_{i-1} \leq D\) なら、\(A_i\) は直前の \(A_{i-1}\) と「似ている」曲です。

したがって、昇順に再生すれば、この曲の違和感スコアは \(0\) にできます。

差が \(D\) より大きい場合

\(A_i - A_{i-1} > D\) の場合を考えます。

このとき、\(A_{i-1}\) 以下の曲と \(A_i\) 以上の曲の間には、必ず \(D\) より大きな差があります。

つまり、この境界をまたぐとき、片方のグループの曲を初めて再生する瞬間には、過去に似た曲が存在しません。

そのため、どのような順番にしても、この境界をまたぐためには少なくとも \(A_i - A_{i-1}\) の違和感コストが必要になります。

昇順に並べれば最適

昇順に再生すると、

• 隣との差が \(D\) 以下なら違和感スコアは \(0\)
• 隣との差が \(D\) より大きければ違和感スコアはその差

になります。

したがって、昇順に並べたときの

\(A_i - A_{i-1} > D\)

を満たす差だけを合計すればよいです。

例えば、

\(A = [1, 3, 10, 12, 20]\), \(D = 2\)

の場合、昇順のまま考えると、

• \(3 - 1 = 2 \leq D\) なのでコスト \(0\)
• \(10 - 3 = 7 > D\) なのでコスト \(7\)
• \(12 - 10 = 2 \leq D\) なのでコスト \(0\)
• \(20 - 12 = 8 > D\) なのでコスト \(8\)

よって答えは

\(7 + 8 = 15\)

です。

素朴に全ての並べ替えを試すと \(N!\) 通りあり、\(N \leq 10^6\) では到底間に合いません。

そこで、ソートして隣同士の差だけを見ることで効率的に解きます。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 答えを \(ans = 0\) とする。
3. \(i = 1\) から \(N-1\) まで見て、
   • \(A_i - A_{i-1} > D\) なら、その差を \(ans\) に加える。
4. \(ans\) を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

ソートが支配的です。

実装のポイント

\(A_i\) や \(D\) は最大 \(10^9\) なので、差や答えは long long 型で扱うと安全です。

また、\(N = 1\) の場合は再生する曲が \(1\) 曲だけなので、違和感の総和は \(0\) になります。ループは自然に実行されず、そのまま \(0\) が出力されます。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D;
    cin >> N >> D;

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

    sort(A.begin(), A.end());

    long long ans = 0;
    for (int i = 1; i < N; i++) {
        long long diff = A[i] - A[i - 1];
        if (diff > D) ans += diff;
    }

    cout << ans << '\n';
    return 0;
}

---

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