Official
D - Diversity of Scores Editorial by yuto1115
解説\(N\) 人の選手たちの得点を多重集合として管理しながら、\(1,2,\dots,T\) 秒後に起きる得点の変動を順に処理していけばよいです。
多重集合を管理できるデータ構造はいくつか存在しますが、この問題では連想配列(C++ の std::map
, std::unordered_map
や python の dictionary など)と呼ばれるデータ構造が有用です。連想配列は通常の配列を拡張したようなもので、通常の配列では添字として \(0,1,2,\dots\) と連続する整数を用いるのに対し、連想配列では添字に好きな値を用いることができます。初期状態では添字が一つも存在せず、添字の追加・削除、特定の添字に対応する値の変更、サイズ(添字の種類数)の取得などの操作が高速に(定数時間やサイズの対数時間などで)行えます。
本問題では、現在の選手たちの得点に現れる各値を添字として用い、添字 \(x\) に対応する値として得点が \(x\) である選手の人数を保持すればよいです。具体的なアルゴリズムは以下の通りです。
- 連想配列 \(M\) を用意する。
- \(M\) に添字 \(0\) を追加し、\(M[0]=N\) とする。
- 各選手の現在の得点を保持する配列 \(C=(C_1,C_2,\dots,C_N)\) を用意し、全ての要素を \(0\) で初期化する。
- \(i=1,2,\dots, T\) の順に以下を行う。
- \(M[C_{A_i}]\) を \(1\) 減らす。
- \(M[C_{A_i}]\) が \(0\) になったならば、 \(M\) から添字 \(C_{A_i}\) を削除する。
- \(C_{A_i}\) に \(B_i\) を足す。
- \(M\) に添字 \(C_{A_i}\) が存在しないならば追加し、\(M[C_{A_i}]=0\) とする。
- \(M[C_{A_i}]\) を \(1\) 増やす。
- 現在の \(M\) のサイズ(添字の種類数)を出力する。
計算量は、下記の実装例のように C++ の std::map
を用いた場合 \(O(N+T\log N)\) になります。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t;
cin >> n >> t;
vector<ll> score(n);
map<ll, int> mp;
mp[0] = n;
for (int i = 0; i < t; i++) {
int a, b;
cin >> a >> b;
--a;
if (--mp[score[a]] == 0) mp.erase(score[a]);
score[a] += b;
++mp[score[a]];
cout << mp.size() << '\n';
}
}
posted:
last update: