LoginSignup
solocomedian
@solocomedian (みやけん)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

AtCoderBeginnerContest343D問題が時間超過になる

解決したいこと

ABC343のD問題で1つ目のソースコードだとサンプルケースではACなのに他の入力ではTLEになりました。なぜ1つ目のコードがTLEになるのか、全てACになった2つ目のソースコードの計算量と比較して教えていただきたいです。

発生している問題・エラー

自分の提出結果
image.png

該当するソースコード

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

1Answer

unorder_setとunorder_mapの計算量について調べた
→以下の記事より値の追加削除所属の判定の平均計算量はどちらもO(logn)になることはわかったが、各プログラムにおける総計算量についてはわからなかった。
https://atcoder.jp/contests/apg4b/tasks/APG4b_aa?lang=ja

こちらですが、間違ってsetmapのデータを見ていませんか?
unordered_setunordered_mapの計算量は以下です。(上記ページから引用)

操作 計算量
値の追加[] 平均$O(1)$
値の削除erase 平均$O(1)$
値へのアクセスat 平均$O(1)$
所属判定count 平均$O(1)$
要素数の取得size $O(1)$

こちらの情報をもとに、全てACになったコードを見ると、diversity_of_scores内の操作の計算量はすべて平均$O(1)$なので、diversity_of_scores自体の計算量も平均$O(1)$です。これを$T$回のループ内で呼び出しているので、ループ部分の計算量は平均で$O(T)$です。さらにvector<long> c(n, 0);の計算量$O(N)$と合わせて、全体の計算量は$O(N+T)$となります。$N$、$T$ともに最大$2 \times 10^5$なので、計算量は最大$4 \times 10^5$となります。

次に、TLEになるコードですが、呼び出しているunordered_setのコンストラクタの計算量は平均$O(N)$です(こちらの計算量の(3)参照)。それを$T$回のループ内で呼び出しているので、全体の計算量は平均で$O(NT)$となります。$N$、$T$ともに最大$2 \times 10^5$なので、計算量は最大$4 \times 10^{10}$となります。

AtCoder の計算量の目安を検索すると、1秒あたり$10^8$と出てくるので、$4 \times 10^{10}$だと TLE になるのも仕方ないと思われます。

0Like

Comments

  1. @solocomedian

    Questioner

    ご回答ありがとうございます。間違ってsetとmapのデータを見ていましたすみません。計算量だけでなくcppのリンクやAtcoderの演算能力の目安を書いて下さったのでしっかり理解できました。

Your answer might help someone💌