C++でいうところのstd::setがPythonにも導入でき、かつAtCoderでも可用なことを最近知った。この記事は、自分自身のための備忘録のようなものであり、万人が参考にできるとは限らないのでご注意ください。

SortedSetおよびSortedList

ローカルで使うにはpip導入後にpip install sortedcontainerを叩くこと。

以下のようなコードを書くと使える。自動補完の際は小文字のsortedsetやsortedlistをimportしないように気をつけよう。

SortedDictもあるらしいが、使い方がよくわからないので割愛。

from sortedcontainers import SortedSet,SortedList

SL = SortedList([3,1,4,1,5])
SS = SortedSet([3,1,4,1,5])

要素の追加がadd、削除がdiscardで統一されていることに注意。

使用例

特徴としては、indexを指定したアクセスが早い。挿入も早い。削除もおそらく早い。
最大・最小値を知りたい時は特に便利。
ACコードへのリンクも記載してあるが、あまりリーダブルではないので注意。

集合を小さい順に見ていって、見たやつから消す、的なことが可能。
余談だが、ソートされていることが保証されているので、集合を小さい順に回すコードを書く際に精神的に良い。ACコード

優先度付きキューの代わりに使うと、「えーと最大値を求めるには$ -1 $をかけて……」みたいな手間が省ける。ACコード

~~1問目にしては妙に難しいことで有名。~~ 二分探索もらくらく。bisectを利用。余談だが、整数列を二分探索する時は、引数から$0.5$を引くと同値に当たるパターンがなくなって精神的に良い。ACコード

「N番目に小さいものを答えよ」系の問題で、Nが十分小さければ使えることがある。
（$\because$集合の長さが必要量をはみ出したら捨てられる）
この問題はPyPyの速さを信じて$116^3$回のループをぶん回した。なぜ116かは忘れた。ACコード

$2\times 10^5$個の幼稚園の管理と、最強園児の管理のため、大量のSortedListを生やした例。制限時間が比較的長いが、それでも割と危うかった。ACコード

集合$A,B$に対し、$\forall a \in A,b \in B \ \lbrack a \le b \rbrack $を保ちつつ要素を出し入れする問題。比較的点数が高かったが、やってみたら通った。嬉しい。ACコード