概要

\(N\) 曲のテンポ値を並べ替えて再生し、違和感スコアの総和を最小化する問題です。テンポ値の差が \(D\) 以下の曲が過去に再生されていれば違和感は \(0\) になり、そうでない場合は直前の曲とのテンポ値の差が違和感となります。

考察

まず、違和感スコアが \(0\) になる条件を整理します。\(j\) 番目（\(j \geq 2\)）の曲の違和感スコアが \(0\) になるのは、「過去に再生された曲の中に、現在の曲とテンポ値の差が \(D\) 以下の曲が存在する」場合です。

テンポ値を昇順にソートして考えると、隣り合う要素の差が \(D\) 以下であれば、それらの曲は互いに「似ている」と言えます。ソートされた配列において、差が \(D\) 以下で繋がっている曲の集まり（連結成分）を一つのグループとみなします。 同じグループ内の曲同士は、直接の差が \(D\) 以下でなくても、間の曲を媒介して似た曲として扱うことができます。したがって、同じグループ内の曲を連続して再生すれば、違和感スコアを \(0\) にすることができます。

一方、異なるグループ間ではテンポ値の差が \(D\) より大きくなります。あるグループから別のグループへ移行するとき、過去に再生された曲はすべて現在の曲と \(D\) より大きく離れているため、必ず違和感スコアが発生します。このときの違和感スコアは「直前の曲のテンポ値との差の絶対値」となります。 違和感の総和を最小にするためには、グループ間の遷移における直前の曲と現在の曲の差を可能な限り小さくする必要があります。ソートされた配列を前から順に見ていくと、前のグループの最大値と次のグループの最小値の差が、遷移時の最小の違和感となります。

アルゴリズム

1. テンポ値の配列 \(A\) を昇順にソートします。
2. 現在のグループにおける最大のテンポ値を R として保持し、初期値を \(A[0]\) とします。
3. 配列を前から順に見ていきます（\(i = 1\) から \(N-1\)）。
   • \(A[i] - A[i-1] \leq D\) の場合、\(A[i]\) は現在のグループに属するため、R を \(A[i]\) に更新します。
   • \(A[i] - A[i-1] > D\) の場合、新しいグループへの移行となります。前のグループの最大値 R と新しいグループの最小値 \(A[i]\) の差が違和感スコアとして発生するため、答えの合計値に \(A[i] - R\) を加算し、R を \(A[i]\) に更新します。
4. 最終的に合計された違和感スコアを出力します。

計算量

• 時間計算量: \(O(N \log N)\) （ソートに支配されます）
• 空間計算量: \(O(N)\) （入力配列を保持するため）

実装のポイント

ソートされた配列を一度走査するだけで、グループ分けと違和感スコアの計算を同時に行うことができます。R という変数一つで「現在のグループの最大値」を管理することで、シンプルかつ効率的に実装できます。

ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    ans = 0
    # 現在の連結成分における最大のテンポ値
    R = A[0]
    
    for i in range(1, N):
        if A[i] - A[i - 1] <= D:
            # 同じ連結成分に属する場合、Rを更新
            R = A[i]
        else:
            # 新しい連結成分に移行した場合、直前の成分の最大値との差を足す
            ans += A[i] - R
            R = A[i]
            
    print(ans)

if __name__ == '__main__':
    solve()

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