AtCoderBeginnerContest343D問題が時間超過になる
解決したいこと
ABC343のD問題で1つ目のソースコードだとサンプルケースではACなのに他の入力ではTLEになりました。なぜ1つ目のコードがTLEになるのか、全てACになった2つ目のソースコードの計算量と比較して教えていただきたいです。
発生している問題・エラー
自分の提出結果
該当するソースコード
TLEになるコード
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
int main()
{
int n, t;
cin >> n >> t;
vector<vector<int>> predict(t, vector<int>(2));
vector<int> a(n, 0);
for (int i = 0; i < t; i++) {
cin >> predict[i][0] >> predict[i][1];
}
for (int i = 0; i < t; i++) {
a[predict[i][0] - 1] += predict[i][1];
unordered_set<int> s(a.begin(), a.end());
cout << s.size() << endl;
}
}
全てACになったコード
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
// 公式の解説に沿った解答
// 連想配列を使って、各要素の出現回数を数える
long diversity_of_scores(unordered_map<long, long> &points, vector<long> &c, long a, long b)
{
points[c[a]] -= 1;
if (points[c[a]] == 0) {
points.erase(c[a]); // mapやvectorの要素はeraseで削除できる
}
c[a] += b;
if (points.find(c[a]) == points.end()) { // findで要素があるかどうかを調べる(findは要素がなければendを返す)
points[c[a]] = 1;
} else {
points[c[a]] += 1;
}
return points.size();
}
int main()
{
long n, t;
cin >> n >> t;
vector<long> c(n, 0);
unordered_map<long, long> points = {
{0, n}
};
for (long i = 0; i < t; i++) {
long a, b;
cin >> a >> b;
cout << diversity_of_scores(points, c, a - 1, b) << endl; // indexに対応付けるためにa-1する
}
}
自分で試したこと
公式解説を参考に2つ目のソースコードを書いた
→プログラムの仕組みはわかったがなぜ2つ目のほうが高速化はよくわからなかった。
unorder_setとunorder_mapの計算量について調べた
→以下の記事より値の追加削除所属の判定の平均計算量はどちらもO(logn)になることはわかったが、各プログラムにおける総計算量についてはわからなかった。
https://atcoder.jp/contests/apg4b/tasks/APG4b_aa?lang=ja
0
