これは数学知識があまりない中１が書いた記事なので計算量などの試算が間違ってる場合があります
間違っていたらコメントしてください
この記事を書いた経緯
ある日、atcoderの優先度付きキューを使う過去問を解いていたら、間違えてbisect.insort使って提出したらTLEしてしまい、その後他の人の解法をみたらsortedcontainers.SortedList(以下SortedList)を使ってました
でSortedListを使う方法でコードを書き直したらACしました
bisect.insortでTLEした問題
そんでもって優先度付きキューの注意点を書きます
heapq
一番ポピュラーな優先度付きキューですね
使い方(n番煎じ)
- heapq.heapqify() リストをソートして初期化
- heapq.heapqpush() 要素を挿入
- heapq.heapqpop() 最小値を取り出す
基本これ使ってたら、問題ないんですが、筆者はおっちょこちょいなのでいつもリストに直でappendしてしまい何度かバグないか、10分ぐらい探すことが多々ありますw
まあ注意して使えば問題ないんですけどね
bisect.insort
こいつが問題児です
使い方
- bisect.insort() 昇順を保ったまま要素を挿入
bisectは便利ですが使い方を間違えるととんでもない目に会います
具体的に挿入時、計算量が$O(N + log N)$みたいな感じになります
例えば$Q$回繰り返すとき、計算量は、先程の式が正しければ分配法則で展開すると$O(QN+(log N)Q)$になります つまり$Q$が$10^5$ぐらいあったら普通にTLEしますね
おそらく内部でリストのinsertメソッドが使わているからでしょう
SortedList
sortedcontainersは標準にしても全然いいと思います
使い方
- A = SortedList() 定義
- A.add() 要素を挿入
- A.bisect_left() 左側の挿入点を返してくれる
- A.bisect_right() 右側の挿入点を返してくれる
特に要素を削除する必要がない場合はSortedListを使ったほうが利便性が高いと思います
最後に
結局 筆者の経験談でしたねw
まあ誰かのお役に立てれば幸いです