概要

テンポ値を昇順に並べたとき、隣り合う値の差が \(D\) を超える場所だけが「どうしても違和感が発生する境目」になります。
答えは、ソート後に隣り合う値の差が \(D\) より大きいものの総和です。

考察

テンポ値を昇順にソートして、

\[ X_1 \leq X_2 \leq \cdots \leq X_N \]

とします。

隣り合う値の差 \(X_{i+1} - X_i\) に注目します。

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

\[ X_{i+1} - X_i \leq D \]

なら、\(X_i\) の直後に \(X_{i+1}\) を再生すれば、\(X_{i+1}\) は直前の曲と似ているので違和感スコアは \(0\) です。

つまり、昇順に再生している限り、差が \(D\) 以下の部分では違和感は発生しません。

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

一方で、

\[ X_{i+1} - X_i > D \]

なら、\(X_i\) 以下の曲と \(X_{i+1}\) 以上の曲は、どれも互いに似ていません。

この境目をまたいで両側の曲をすべて再生するためには、どこかで必ず「似ている曲が過去に存在しない曲」を再生する必要があります。

そのとき、少なくともこの差

\[ X_{i+1} - X_i \]

だけの違和感が発生します。

昇順に再生すると最適

実際に昇順に再生すると、

• 差が \(D\) 以下の部分では違和感スコア \(0\)
• 差が \(D\) より大きい部分では違和感スコアがその差そのもの

になります。

したがって、昇順に並べたときの「\(D\) より大きい隣接差」の総和が答えになります。

例えば、

\[ A = [1, 3, 4, 10, 12], \quad D = 2 \]

の場合、ソート後の隣接差は

\[ 2, 1, 6, 2 \]

です。

このうち \(D=2\) より大きいのは \(6\) だけなので、答えは \(6\) です。

実際に

\[ 1 \to 3 \to 4 \to 10 \to 12 \]

と再生すると、\(4\) から \(10\) に移るときだけ違和感が発生します。

素朴に全ての再生順を試すと \(N!\) 通りあり、\(N \leq 10^6\) では不可能です。
また、各曲について過去の曲をすべて調べる方法も \(O(N^2)\) となり間に合いません。

しかし、ソートして隣接差を見るだけで十分です。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 隣り合う要素の差を順に見る。
3. 差が \(D\) より大きければ、その差を答えに加える。
4. 最後に答えを出力する。

つまり、答えは次の値です。

\[ \sum_{i=1}^{N-1} \begin{cases} A_{i+1} - A_i & \text{if } A_{i+1} - A_i > D \\ 0 & \text{otherwise} \end{cases} \]

ただし、ここでの \(A\) はソート後の配列です。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • その後の走査に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するため

実装のポイント

\(N\) が最大 \(10^6\) と大きいので、入力は高速に行う必要があります。

Python では sys.stdin.buffer.read() を使うと高速です。

また、答えは最大でかなり大きくなる可能性がありますが、Python の int は任意精度なのでそのままで問題ありません。C++ などで実装する場合は long long を使う必要があります。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, D = map(int, input().split())
    A = list(map(int, sys.stdin.buffer.read().split()))
    A.sort()

    ans = 0
    prev = A[0]
    for x in A:
        diff = x - prev
        if diff > D:
            ans += diff
        prev = x

    print(ans)

if __name__ == "__main__":
    main()

---

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