Count Points Parallel To Y

2 secs 1024 MB

はじめに

Pythonのdict(defaultdict)やC++のunordered_mapの各アクセスの計算量の平均時間計算量は $O(1)$ です。しかし、これらの内部のデータ構造の内部を意識した意図的な入力に対して $O(N)$ となることがあります。

map(C++)や二分探索で数える(Python)で各計算量を $O(logN)$ とすることができます。

翻訳: unordered_mapのハッシュ衝突攻撃とその対策 (neal: Blowing up unordered_map, and how to stop getting hacked on it) の通りです。AtCoder C++20, C++23 gcc12.2 や MojaCoder のC++では85229の倍数を与えることでハッシュが衝突し各アクセスが $O(N)$ となりTLEします。

unordered_mapではなくmapを使うと各アクセスが $O(logN)$ で可能になります。

Qiitaに書きました。