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問題で使用（実際には2¹⁶は64*1024=10⁵程度のオーダーしか無いので十分扱えたが…）

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（参考）で求められる。