Part3 [応用編]プロコン必携ライブラリ

多くのプログラミングコンテストでは、STLなどの標準ライブラリ以外のライブラリファイルをインクルードして使用することができません。
そこで、その場で描くことが難しいアルゴリズムや典型問題の解法などは、自らあらかじめライブラリとして準備しておき、有効活用します。

そういうものなんだな
STLと同等のことは、組み込みの型と標準ライブラリで対応できてたかな？

スタック：listまたはdeque
双方向リスト：だいたいはdequeでいけるかな？前後自由自在に動き回ることはできないかも？
キュー：deque、またはlistとちょっとの手間
可変長配列：listそのもの
二分探索：bisect
ハッシュテーブル・map：dict
ソート：list.sort()またはsorted()
集合：set
優先度付きキュー：heapq

list.sort()はTimsortっていうstableなアルゴリズムを使っているらしい
マージソートと挿入ソートのハイブリッドで、いろんなデータで効率良く働くそうな
普通に使っていいような気がする

ドキュメントも見ておこう

list：4.6. シーケンス型 — list, tuple, range
deque：8.3.3. deque オブジェクト
bisect：8.6. bisect — 配列二分法アルゴリズム
dict：4.10. マッピング型
sort：listのドキュメントおよびソート HOW TO
set：4.9. set（集合）型 — set, frozenset
heapq：8.5. heapq — ヒープキューアルゴリズム

二分木とかグラフ構造は標準ライブラリにはなさそうだ
STLにあるかどうかは確認してないけど、少なくとも本では紹介されていない
十分整備されていると思ってよさそうだ
さすがBatteries Included

アルゴリズムをコレクションしていく楽しみがあります

マニアックな喜び