Python2で競技プログラミングする時に知っておきたいtipsの，ライブラリについての部分を分割しました．
Pythonのバージョンは2.7.5（Python3では，入出力などの仕様が大きく異なるので，他の記事を参照することをおすすめします）．
少しマイナーだが，自分が使っていて便利だと感じたライブラリを挙げる．
数学関数の集合math
いずれ書く．
順列，組合せなどが得られるitertools
9.7. itertools — 効率的なループ実行のためのイテレータ生成関数
Python で組み合わせや順列を得るときは itertools を使う | CUBE SUGAR STORAGE
イテレータを生成するメソッドが詰まったライブラリ．
競技プログラミングでは，順列，組合せを生成する際に重宝する(C++におけるnext_permutationなどに相当)．
自分で多重ループを回すなどするより非常に高速に動作するので，積極的に使っていくべき．
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
# lから要素を2つ選んで並べる
# 重複は考慮しない
# 順序は考慮する(順列)
for elem in itertools.permutations(l, 2):
print elem # elemには並べた要素のタプルが代入される
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
# lから要素を3つ選んで並べる
# 重複は考慮しない
# 順序は考慮しない(組合せ)
for elem in itertools.combinations(l, 3):
print elem
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)
ちなみに，重複を考慮した組合せや，デカルト積(直積)も求めることができる．
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
# lの各要素を取り出したものの2つ組を並べる
# 重複は考慮する
# 順序は考慮しない
for elem in itertools.product(l, repeat=2):
print elem
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 3)
(3, 4)
(3, 5)
(4, 4)
(4, 5)
(5, 5)
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
# lの各要素を取り出したものの2つ組を並べる
# 重複は考慮する
# 順序は考慮する
for elem in itertools.product(l, repeat=2):
print elem
# 上のコードは下記のコードと等価
for a in l:
for b in l:
print (a, b)
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
(5, 5)
collections
8.3. collections — 高性能なコンテナ・データ型 — Python 2.7ja1 documentation
Pythonのcollectionsモジュールが地味に便利 - 唯物是真 @Scaled_Wurm
defaultdict
collections.defaultdictは，その名の通り，デフォルト値を持つdict．
競技プログラミングでは，カウンタを作成する機会が多い(特に実装ゲー問題に多い)．
例えば，入力に存在する英単語について，その頻度を求めるような問題が出題された際には，dictを用いてそれぞれの単語に対応したカウンタを作る必要があるが，dictは，キーを初期化しないとエラーが出るため面倒．
defaultdictを使うことで，初期化を減らし，コードを見やすくすることができる．
from collections import defaultdict
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
# dictの場合
d = {}
for e in l:
# 毎回キー値があるかをチェックし，ない場合は初期化する必要がある
if e in d.keys():
d[e] += 1
else:
d[e] = 1
print d # {'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2}
dd = defaultdict(int) # すべてのキーが0で初期化される
for e in l:
dd[e] += 1 # 初期化の必要がない
print dd # defaultdict(<type 'int'>, {'be': 2, 'that': 1, 'is': 1, 'question': 1, 'to': 2, 'not': 1, 'the': 1, 'or': 1})
print dd['be'] # 2
dd2 = defaultdict(list) # すべてのキーが[]で初期化される
dd2['a'].append(1)
print dd2 # defaultdict(<type 'list'>, {'a': [1]})
カウンタ作成に重宝するCounter
collections.Counterは，カウンタ作成に特化したオブジェクトで，自動的に0が初期値とされる．
これだけだとdefautdict(int)と等価だが，最大値をすぐに求められるなど，他にもいくつか便利機能がある．
from collections import Counter
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
c = Counter()
for e in l:
c[e] += 1
print c # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
print c['be'] # 2
# リストなどを引数に渡すと，自動的にカウントされる
c2 = Counter(l)
print c2 # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
# カウンタの値の降順にソート
print c.most_common() # [('be', 2), ('to', 2), ('that', 1), ('is', 1), ('question', 1), ('not', 1), ('the', 1), ('or', 1)]
# カウンタの値が最大のものから順に3つを出力
print c.most_common(3) # [('be', 2), ('to', 2), ('that', 1)]