概要

\(N\) 曲を任意の順序で再生したとき、「過去に再生した曲とテンポ値の差が \(D\) 以下である」という条件を満たさない曲に対してのみペナルティが加算される問題で、ペナルティの総和を最小化する再生順序を求める問題です。

考察

まず、テンポ値をソートし、隣り合う曲の差が \(D\) 以下である曲同士を連結してグループ（連結成分）に分けます。同じグループ内の曲は、昇順（または降順）に再生することで、2曲目以降は必ず直前の曲との差が \(D\) 以下になります。したがって、同じグループ内の曲を連続して再生すれば、グループ内で発生する違和感スコアは \(0\) になります。

グループ間の移動については、あるグループの曲から別のグループの曲へ移る際、必ず違和感スコアが発生します。スコアを最小化するためには、グループ間の行き来を最小限にする必要があるため、各グループを1つのブロックとして連続再生するのが最適です。

ここで、各グループには「最小値 \(L\)」と「最大値 \(R\)」があります。グループを昇順に再生すれば最初の曲が \(L\)、最後の曲が \(R\) となり、降順に再生すれば最初の曲が \(R\)、最後の曲が \(L\) となります。つまり、あるグループの終端は \(L\) か \(R\) のいずれかになります。 前のグループの終端から次のグループの始端への遷移コストを最小化するために、動的計画法（DP）を用います。

アルゴリズム

1. 配列 \(A\) を昇順にソートします。
2. 隣り合う要素の差が \(D\) 以下である曲を同じグループとして分割します。各グループの最小値を配列 L、最大値を配列 R に格納します。
3. DP配列を以下のように定義します。
   • dp0: \(i\) 番目のグループまでを再生し終え、最後の曲が L[i] であるときの違和感スコアの最小値
   • dp1: \(i\) 番目のグループまでを再生し終え、最後の曲が R[i] であるときの違和感スコアの最小値
4. 初期状態（0番目のグループ）では違和感は0なので、dp0 = 0, dp1 = 0 とします。
5. \(i\) 番目のグループへの遷移は以下のようになります。
   • 現在のグループを昇順に再生し R[i] で終わる場合、始端は L[i] です。前のグループの終端が L[i-1] のときと R[i-1] のときで遷移コストが異なります。 next_dp1 = min(dp0 + |L[i] - L[i-1]|, dp1 + |L[i] - R[i-1]|)
   • 現在のグループを降順に再生し L[i] で終わる場合、始端は R[i] です。同様に計算します。 next_dp0 = min(dp0 + |R[i] - L[i-1]|, dp1 + |R[i] - R[i-1]|)
6. 全てのグループについてDPを更新し、最終的な min(dp0, dp1) が答えになります。

計算量

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

実装のポイント

• \(N\) が \(10^6\) と大きいため、入出力を高速化する（C++では ios_base::sync_with_stdio(false); cin.tie(NULL); などを用いる）必要があります。

• PythonのつもりでC++を書いて絶対値を abs() に頼ると、long long 型のオーバーフローや意図しない挙動を避けるため、直接条件分岐で正負を反転させるか、std::abs を適切に使用します（提供コードではif文による反転を利用しています）。

• グループ数が1つの場合はグループ間の遷移が発生しないため、違和感スコアは0になります。

  ソースコード

#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;
    cin >> N >> D;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    
    vector<long long> L, R;
    for (int i = 0; i < N; ) {
        int j = i;
        while (j + 1 < N && A[j+1] - A[j] <= D) {
            j++;
        }
        L.push_back(A[i]);
        R.push_back(A[j]);
        i = j + 1;
    }
    
    int M = L.size();
    if (M == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    long long dp0 = 0; // ends at L[i-1]
    long long dp1 = 0; // ends at R[i-1]
    
    for (int i = 1; i < M; i++) {
        long long r_minus_l_prev0 = R[i] - L[i-1]; if (r_minus_l_prev0 < 0) r_minus_l_prev0 = -r_minus_l_prev0;
        long long r_minus_r_prev1 = R[i] - R[i-1]; if (r_minus_r_prev1 < 0) r_minus_r_prev1 = -r_minus_r_prev1;
        long long l_minus_l_prev0 = L[i] - L[i-1]; if (l_minus_l_prev0 < 0) l_minus_l_prev0 = -l_minus_l_prev0;
        long long l_minus_r_prev1 = L[i] - R[i-1]; if (l_minus_r_prev1 < 0) l_minus_r_prev1 = -l_minus_r_prev1;
        
        long long next_dp0 = min(dp0 + r_minus_l_prev0, dp1 + r_minus_r_prev1);
        long long next_dp1 = min(dp0 + l_minus_l_prev0, dp1 + l_minus_r_prev1);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }
    
    cout << min(dp0, dp1) << endl;
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。