B - プレイリストの最適化 / Playlist Optimization 解説
by 
MMNMM
\(A _ i\) を事前に並べ替えておいても答えは変わらないので、\(A _ 1\le A _ 2\le\ldots\le A _ N\) として一般性を失いません（つまり、事前に \(A\) をソートしておくことを考えます）。
違和感スコアに \(|B _ i-B _ {i-1}|\) が加算されたとき、数直線上の区間 \([\min\lbrace B _ i,B _ {i-1}\rbrace,\max\lbrace B _ i,B _ {i-1}\rbrace]\) に色を塗ることとします。
\(A _ i+D\lt A _ {i+1}\) が成り立つとき、区間 \([A _ i,A _ {i+1}]\) には色が塗られていなければなりません。
証明
\(i+1\) 以上の曲のうちはじめて再生される曲 \(j\) が全体で最初に再生される曲ではないとき、かならず違和感スコアへの加算が行われます（すでに再生されている曲のテンポ値ははすべて曲 \(j\) のテンポ値より \(D+1\) 以上小さいです）。 このとき色が塗られる区間は \([A _ i,A _ {i+1}]\) を含んでいます。
\(i+1\) 以上の曲のうちはじめて再生される曲 \(j\) が全体で最初に再生される曲であるときは \(i\) 以下の曲について同様の議論が行え、示されました。
違和感スコアは色が塗られている区間の長さの合計以上なので、違和感スコアの下界として「\(A _ i+D\lt A _ {i+1}\) が成り立つような \(i\) に対する \(A _ {i+1}-A _ i\) の総和」を取ることができます。
この下界は \(A\) を昇順にソートすることで達成できるので、あとはこれを計算すればよいです。
ソートがボトルネックとなり、時間計算量は \(O(N\log N)\) となります。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, D;
cin >> N >> D;
vector<int> A(N);
for (int& a : A) {
cin >> a;
}
ranges::sort(A); // 昇順にソート
int ans = 0;
for (int i = 0; i + 1 < N; ++i) { // 隣接する曲について
if (A[i] + D < A[i + 1]) { // 差が D より大きければ
ans += A[i + 1] - A[i]; // スコアを増やす
}
}
cout << ans << endl;
return 0;
}
N, D = map(int, input().split())
A = sorted(map(int, input().split())) # 昇順にソート
ans = 0
for A, B in zip(A, A[1:]): # 隣接する曲について
if A + D < B: # 差が D より大きければ
ans += B - A # スコアを増やす
print(ans)
投稿日時:
最終更新: