Python2で競技プログラミングする時に知っておきたいtipsの，データ構造についての部分を分割しました．
Pythonのバージョンは2.7.5（Python3では，入出力などの仕様が大きく異なるので，他の記事を参照することをおすすめします）．
int
整数型．
厳密に言うと，Pythonの整数には，整数型のintと長整数型のlongがあるが，
- RubyのFixnumとBignumのように境界値によって自動的に型変換される
- JavaのBigIntegerのように整数型と長整数型で使えるメソッドに差異があるわけではない
という理由から，あまり気にする必要はない．
文字列を整数に変換する
print int('10') # 10
この辺りはすごく簡潔で好き．
基数変換
整数の基数変換はプロコン頻出．
@n_knuu6 さんに教えていただきました．
format()を使うことにより，10進数から2/8/16進表現された文字列への変換ができる．
# 2進数
b = format(10, 'b') # '1010'
# 8進数
o = format(10, 'o') # '12'
# 16進数(小文字)
x = format(10, 'x') # 'a'
# 16進数(大文字)
X = format(10, 'X') # 'A'
逆に，2/8/16進数表現された文字列から10進数への変換がしたい場合は，int()の第2引数に元の文字列の基数を指定するとよい．
d1 = int('1010', 2) # 10
d2 = int('12', 8) # 10
d3 = int('a', 16) # 10
d4 = int('A', 16) # 10
ビット演算
いずれ書く．
float
浮動小数点型．
文字列を浮動小数点に変換する
print float('10.00') # 10.0
除算の結果が浮動小数点になる場合の処理
浮動小数点関係でよくハマるのは以下の点．
# 除算の余りが切り捨てられる
a = 5 / 2 # 2
整数同士の除算結果が整数以外の値になる場合，結果が切り捨てられる(Python3ではこの問題が解決されているらしい)．
整数同士の除算を正しく表現したい場合は，
a1 = 5 * 1.0 / 2 # 2.5
a2 = 5. / 2 # 2.5
a3 = float(5) / 2 # 2.5
のように，分子，分母どちらかをfloat型にするとよい．
無限大を扱う
競技プログラミングではよく使う，無限大．
もちろん，10000000000などの非常に大きな整数値を無限大として設定することも可能だが，入力値によっては設定した値を超えてしまう可能性があるなど，思わぬバグの原因になる．
Pythonでは，float('inf')によって無限大を表すことができる．
p_inf = float('inf') # 正の無限大
print p_inf > 10000000000 # True
print p_inf + 10000000000 # inf
print p_inf - 10000000000 # inf
print min(10000000000, float('inf')) # 10000000000
n_inf = -float('inf') # 負の無限大
print n_inf < -10000000000 # True
print float('inf') - float('inf') # nan
print float('inf') / float('inf') # nan
print float('inf') * 0 # nan
上記のように，無限大同士で減算，除算を行ったり，無限大に0をかけると，値がnan(不定)になることに注意．
str
文字列型．
Javaなどと同様，文字列の変更(文字列を構成する要素への再代入)はできないことに気をつける．
逆順の文字列を出力する
すごくよく使う(けどすぐに忘れる)．
s = 'abc'
reverse = s[::-1] # 'cba'
文字列と，文字列の各文字からなるリストの変換
これもよく使う．
s = 'abc'
l = list(s) # ['a', 'b', 'c']
ns = ''.join(l) # 'abc'
ns2 = ','.join(l) # 'a,b,c'
# ちなみに，str(l)は逆演算にならない
bad = str(l) # "['a', 'b', 'c']"
英数字からASCIIコードを取得する
競技プログラミングだと，文字からASCIIコードを取得することも多い(有名なものだとシーザー暗号とか)．
c = 'a'
print ord('a') # 97
# 2文字以上の文字列や，ASCIIコードで表せない文字を引数に加えるとエラー
print ord('ab') # TypeError
list
いわゆる配列(厳密に言うとPythonにもarrayモジュールがあるので間違いだけど，よほどの高速化が必要でない限りはリストを用いると良い)．
わりといろんな機能がある．
5. データ構造 — Python 2.7ja1 documentation
リスト - 作成、取り出し、置換、追加、検索、削除、要素数 - ひきメモ
基本的なことは上記のページに書いてあるので省略．
初期化
要素数が少なければそのまま代入すればよいが，例えば，C++における
int a[100][100];
みたいなことをどうするか．
1次元リストの初期化
リスト内包表記による初期化と，*による初期化がある．
# どちらも0が100個続くリスト([0, 0, ..., 0])を変数lに代入する
l = [0 for i in range(100)] # リスト内包表記を用いた初期化
l = [0] * 100 # *を用いた初期化
ちなみに，ipythonの%timeitを用いて，実行時間を比較したところ，
In [45]: %timeit [0] * 1000000
100 loops, best of 3: 6.66 ms per loop
In [46]: %timeit [0 for i in range(1000000)]
10 loops, best of 3: 65.1 ms per loop
となり，*を用いた初期化の方が高速であることがわかった．
2次元リストの初期化
ここで，10*10の2次元リストを生成するために，
l = [[0] * 10] * 10
とするのは間違い．
リストに対して*を用いると，リストの参照がコピーされるため，
l = [[0] * 10] * 10
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [1, 0, 0, ..., 0],
# ...
# [1, 0, 0, ..., 0]]
のように，変更が他の箇所にも波及してしまう．
ここはわりとハマりどころ．
正しくは，
l = [[0] * 10 for i in range(10)]
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
# [0, 0, 0, ..., 0],
# ...
# [0, 0, 0, ..., 0]]
または，
l = [[0 for j in range(10)] for i in range(10)]
とする．
3次元以上についても同様．
これについても実行時間のベンチマークをとったところ，
In [40]: %timeit [[0] * 1000 for i in range(1000)]
100 loops, best of 3: 7.04 ms per loop
In [42]: %timeit [[0 for j in range(1000)] for i in range(1000)]
10 loops, best of 3: 48 ms per loop
のように，使えるところでは*を使った方がいいらしいことがわかった．
リスト内包表記
5. データ構造 — Python 2.7ja1 documentation
Python のリスト内包表記 - Ruby や Haskell の書き方と比べながら | すぐに忘れる脳みそのためのメモ
リストに対して演算するためのPython独特な記法．
Pythonの言語仕様にしては若干学習コストが高い気もするが，簡潔かつ強力な表現が可能なため，覚えておいて損はないと思う．
上記の例でも挙げられている通り，map()，filter()の代わりに使うとよい．
l = range(5) # [0, 1, 2, 3, 4]
x = [2 * e for e in l if e >= 3] # lの要素のうち，3以上のもののみを取り出し(filter)，それを2倍したものの集合をリストとして返す(map)
print x # [6, 8]
多次元リストにも適用可能．
l = [[0] * 10 for i in range(10)]
x = [[e + 1 for e in l[i]] for i in range(len(l))] # リストのすべての要素に1を足す
print l
# [[1, 1, ..., 1],
# [1, 1, ..., 1],
# ...
# [1, 1, ..., 1]]
forループを短く書いたりもできる．
一般的にリスト内包表記の方が高速．
l = []
for i in range(10):
for j in range(10):
l.append((i, j))
print l
# [(0, 0),
# (0, 1),
# (0, 2),
# ...
# (9, 8),
# (9, 9)]
# 上記のコードが1行で書ける
print [(i, j) for i in range(10) for j in range(10)]
以下のようにネストもできるが，複雑になる場合が多いためあまりオススメしない．
l = range(5) # [0, 1, 2, 3, 4]
x = [e for e in [2 * e for e in l if e >= 3] if e > 7] # lの要素のうち，3以上のもののみを取り出し，それを2倍したものの集合について，7より大きいもののみをリストとして返す
print x # [8]
ソート
非破壊的なsorted()関数と，破壊的なsort()メソッドがある．
sorted(), sort()の両方について，デフォルトでは昇順ソートされるが，引数にreverse=Trueを渡すことで，降順ソートに変更できる．
ソートの対象となる要素が文字列であれば，辞書順にソートされる．
l = [5, 1, 3, 4, 2]
print sorted(l) # [1, 2, 3, 4, 5]
print l # [5, 1, 3, 4, 2]
print l.sort() # None
print l # [1, 2, 3, 4, 5]
l.sort(reverse=True)
print l # [5, 4, 3, 2, 1]
リストの各要素がタプルだった場合，デフォルトでは，各要素の0番目の要素についてソートした上で，同じ値だったものについて，1番目の要素についてソート…ということを繰り返す．
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
引数にkey="lambda式"を与えることで，キーを指定したソートも可能．
l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]
# l2について，下記の2つは等価
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
print sorted(l2, key=lambda x: (x[0], x[1])) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
# 第2要素について降順ソートし，同じ値だったものについては第1要素について昇順ソートする
print sorted(l2, key=lambda x: (-x[1], x[0]) # [('fuga', 3), ('piyo', 2), ('fuga', 1), ('hoge', 1)]
setとdict
いずれ書く．
スタック/キュー
Pythonでは，listオブジェクトがスタック，キューの役目を果たしている．
l = [0, 1, 2, 3]
# push/enque
l.append(4)
print l # [0, 1, 2, 3, 4]
# pop
x = l.pop() # 4
print l # [0, 1, 2, 3]
# deque
y = l.pop(0) # 0
print l # [1, 2, 3]
追記：
@wonderful_panda さんに教えていただきました．
8.3. collections — 高性能なコンテナ・データ型 — Python 2.7ja1 documentation
append()やpop()は$O(1)$だが，pop(0)は$O(n)$の操作であるため，リストの要素数が多くなるとdequeに時間がかかるようになってしまう．
(スタック，)キューを使う場合は，collections.dequeを使うのが安全．
from collections import deque
l = [0, 1, 2, 3]
q = deque(l)
# push/enque
q.append(4)
print q # deque([0, 1, 2, 3, 4])
# pop
x = q.pop() # 4
print q # deque([0, 1, 2, 3])
# deque
y = q.popleft() # 0
print q # deque([1, 2, 3])
プライオリティキュー
Pythonでダイクストラアルゴリズムを実装した - フツーって言うなぁ！
競技プログラミングではそこそこお世話になるプライオリティキュー(優先度付きキュー)．
以前，ブログに記事を書いたので，そちらを参照．