Pythonで競技プログラミング(プロコン)
今更ではあるが今後AtCoderの問題を解く上で使ったライブラリとか手法とかを
ここにまとめていこうと思う。python限定。
入出力
基本
i = input() x,y = map(int,raw_input().split())
応用
複数行を一気に読んで、入出力のオーバーヘッドを無くせる。
(行数が多い時、稀にこれをしないとTLEになる。)
lines = sys.stdin.readlines()
因みにローカルで実行するときは<ctrl-d>
とかでEOFを検知させる必要が有る。
ローカルでの実行
クリップボードにテストデータ(テキスト)コピーしたあと、
以下で簡単に実行できる。
pbpaste| python test.py
問題が難しくて、テストデータを何回も使いそうだと思った場合は、
ファイルに書き出しておく。
pbpaste > dataset1 pbpaste > dataset2 python test.py < dataset1 python test.py < dataset2
ライブラリ
heapq
優先順位付きキューを実現するモジュール。 Donutsコン2015C問題などで使用したが、すごく使う機会が多い。 基本的に「要素を追加・最小値を削除」が継続的に必要な時に使う。
from heapq import heappush, heappop, heapify heap = [2,3,7,1] heapify(heap)
以下の3つの機能に対応する操作がある。
キューに対して要素を優先度つきで追加
heappush(heap,element)
最も高い優先度を持つ要素をキューから取り除き、それを返す
heappop(heap)
最も高い優先度を持つ要素を取り除くことなく参照
heap[0]
itertools
組み合わせや順列を使うときは、素直にライブラリを使うのが良さげ。 Donutsコン2015のB問題で使用(実際には216は64*1024=105程度のオーダーしか無いので十分扱えたが…)
Python で組み合わせや順列を得るときは itertools を使う | CUBE SUGAR STORAGE
- 5C2だと
itertools.combinations([1,3,4,6,7],2)
Union-Find
Makoto Hiroiのページを参考にしました。
ARC#032のB問題で使用。
class UnionFind3: def __init__(self, size): # 負の値はルート (集合の代表) で集合の個数 # 正の値は次の要素を表す self.table = [-1 for _ in xrange(size)] # 集合の代表を求める def find(self, x): if self.table[x] < 0: return x else: # 経路の圧縮 self.table[x] = self.find(self.table[x]) return self.table[x] # 併合 def union(self, x, y): s1 = self.find(x) s2 = self.find(y) if s1 != s2: if self.table[s1] <= self.table[s2]: # 小さいほうが個数が多い self.table[s1] += self.table[s2] self.table[s2] = s1 else: self.table[s2] += self.table[s1] self.table[s1] = s2 return True return False def main(): lines = sys.stdin.readlines() n,m = map(int,lines[0].split()) uf = UnionFind3(n) for line in lines[1:]: a,b = map(int,line.split()) uf.union(a-1,b-1) size = 0 for v in uf.table: if v < 0: size += 1 print(size-1) main()
最初self.table
にはsize個の-1が入っている。
これは、要素数1の集合がsize個あるということ。
負の値を持つのはルートだけなので、負の個数を調べれば素集合の数がわかる。
nCr mod m(コンビネーションのmodulo計算)
プロコンでは組み合わせnCrの計算結果を出力させる際に、数が大きくなっても大丈夫なようにmodulo計算させる場合が多い。
(ARC#039のB問題など)
def modc(a,b,m): c = 1 for i in xrange(b): c = c * (a - i) % m c = c * modinv(i + 1,m) % m return c def egcd(a, b): (x, lastx) = (0, 1) (y, lasty) = (1, 0) while b != 0: q = a // b (a, b) = (b, a % b) (x, lastx) = (lastx - q * x, x) (y, lasty) = (lasty - q * y, y) return (lastx, lasty, a) def modinv(a, m): (inv, q, gcd_val) = egcd(a, m) return inv % m
nCr mod m
はmodc(n,r,m)
で得られる。
modulo(合同式)の四則演算
- 加算:(a + b) mod m = (a mod m) + (b mod m)
- 減算:(a - b) mod m = (a mod m) - (b mod m)
- 乗算:(a * b) mod m = (a mod m) * (b mod m)
- 除算:(a / b) mod m = (a mod m) * b'
- b'はb mod mの逆元(逆数)で、上記のmodinv(参考)で求められる。