Pythonでプログラミングコンテストに出てみよう! - mitsu_koh notebook

これは以前 Python 歴数ヶ月もない僕がコンテストでよく使うだろうと思われるコードをまとめたものです。
こういうまとめが欲しいなと思ったのですが見つけられませんでした。
調べながら書いているので間違っているところがあるかもしれません。
Python のバージョンは 2.6.5 です。3 以降とはけっこう違うところがあるので注意してください。

TODO

• 入出力
• メモ化再帰
• イテレーター

おまじない

#!/usr/bin/env python
# coding: utf-8

? 演算子

1 if True else 0    # 1

配列 a[2][5] の宣言

a = [0 for i in xrange(2) for j in xrange(5)]

スタック

s = []
s.append(100)   # push 100
s.pop()         # pop and return 100

キュー

q = []
q.append(100)   # push 10
q.pop(0)        # pop and return 100

プライオリティキュー

from heapq import heapify,heappush,heappop 
pq = []
heapify(pq)         # change to heap from list
heappush(pq, 10)    # push 10
heappop(pq)         # pop and return 10

map

d = dict()
d = {'a':0, 'b':1}
d = dict(a=0, b=1)
d = dict([['a', 0], ['b', 1]])
len(d)          # size
d['c'] = 2      # set key and value
d.get('a', -1)  # return d['a'] if 'a' in d else -1
d.pop('a', -1)  # if d has key 'a', remove key 'a' and return d['a']
                # if d don't have key 'a', return -1
d.clear()       # clear
'a' in d        # check if d has key 'a'
'a' not in d    # check if d don't have key 'a'
d.keys(), d.iterkeys()      # return key list (iter: an iterator over the keys)
d.values(), d.itervalues()  # return value list (iter: an iterator over the values)
d.items(), d.iteritems()    # return (key, value) (iter: an iterator over the items)

set

st = set()
st = set([0, 1, 2, 3])
len(st)         # size
st.add(10)      # insert 10
st.remove(10)   # remove 10 (raises KeyError if not 10 in st)
st.discard(10)  # remove 10 (don't raise KeyError if 10 not in st)
st.clear()      # clear
10 in st        # check if st has 10
10 not in st    # check if st don't have 10

配列のソート

import operator
a = []
a.sort()
a.sort(reverse=True)        # reverse sort
a.sort(cmp=lambda x, y: -1 if x < y else (0 if x == y else 1))  # sort with comparator
a.sort(key=lambda x: x)     # sort with function which returns a key
a.sort(key=operator.attrgetter('key'))  # sort with function which returns the key

２分探索

from bisect import bisect_right, bisect_left
a = [ 0, 1, 1, 2, 2, 2, 2, 3, 3, 3 ]
bisect_left(a, 2)       # 3 (lower_bound)
bisect_left(a, 100)     # 10 
bisect_right(a, 2)      # 7 (upper_bound)
bisect_right(a, 100)    # 10
bisect_right(a, 2) - bisect_left(a, 2) # 4 (a.count(2))