unorder_setとunorder_mapの計算量について調べた
→以下の記事より値の追加削除所属の判定の平均計算量はどちらもO(logn)になることはわかったが、各プログラムにおける総計算量についてはわからなかった。
https://atcoder.jp/contests/apg4b/tasks/APG4b_aa?lang=ja
こちらですが、間違ってset
とmap
のデータを見ていませんか?
unordered_set
とunordered_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 になるのも仕方ないと思われます。