読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

定数倍を高速化するお話し

実装メモ

ただの経験則でベンチマークをしたわけではないが
結構重要だと思うのでメモ

mapを使った座圧とsortを使った座圧

mapを使ったほうが実装は百倍楽です.
しかし二分平衡探索木の挿入のlogが重いのか,結構遅い.
面倒だけど配列にぶち込んでstd::sortしてごにょごにょしてあげたほうが速いかもです.

priority_queue

ダイクストラ法などでみなさんお世話になるであろうpriority_queue,二分ヒープのお話し
内部実装がvectorになっているので挿入を繰り返した時の動的確保が遅い?
自前のヒープを作ったところ定数倍が改善された問題がいくつかありました.
reserveメソッドぐらい用意しておいてほしいです.

cin,cout

ギリギリそうな問題は使うのやめましょう

座圧するデータ構造作ろうかなあ