細かい説明を省略する。Classとメイン関数をみれば、なんとなく使い方についてわかるだろうから。

# *******************************************
# Dinic's Max Flow Algorithm
# *******************************************
class MaxFlow:
    def __init__(self, V):
        self.V = V
        self.level = [0] * V
        self.iter = [0] * V
        self.edge = [[] for i in range(V)]

    def add_edge(self, fr, to, cap):
        f, t = len(self.edge[fr]), len(self.edge[to])
        self.edge[fr].append([to, cap, t])
        self.edge[to].append([fr, cap, f])

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        Q = []
        Q.append(s)
        while Q:
            v = Q.pop()
            for to, cap, rev in self.edge[v]:
                if cap > 0 and self.level[to] < 0:
                    self.level[to] = self.level[v] + 1
                    Q.append(to)

    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.edge[v])):
            to, cap, rev = self.edge[v][i]
            if cap > 0 and self.level[v] < self.level[to]:
                d = self.dfs(to, t, min(f, cap))
                if d > 0:
                    self.edge[v][i][1] -= d
                    self.edge[to][rev][1] += d
                    return d
            self.iter[v] = i
        return 0

    def maxFlow(self, s, t, INF=10**8):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0: break
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f <= 0: break
                flow += f
        return flow

N, M = map(int, input().split())
d = MaxFlow(N)
for i in range(M):
	x, y = map(int, input().split())
	d.add_edge(x, y, 1)
source, sink = map(int, input().split())
print(d.maxFlow(source, sink))

Python3で書いたはじめてのクラスなので、もっと簡潔な表現ができるかもしれないが、自己メモとして置いておく。

Union Setは2つの要素が同一集合に属するかどうか、効率的に判定できるアルゴリズム。構造が簡単で、競プロではよく見かける。

使い方は簡単。
u = UnionSet(nmax)  # クラスの生成。nmaxは集合の最大値
u.unite(a, b)  # 整数 a, b を同一集合にする
u.connected(a, b)  # 整数 a, b は同一集合に属するかどうかを聞く
u.root(a)  # 整数 a が属する集合の代表値(ルート値)

以下はコード。AOJ-ALDS1_11_Dに対する解答でもある。

# AOJ ALDS1_11_D Connected Components
# Python3 2018.6.23 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

n, m = map(int, input().split())
u = UnionSet(n)
for i in range(m):
	s, t = map(int, input().split())
	u.unite(s, t)
q = int(input())
for i in range(q):
	s, t = map(int, input().split())
	print("yes" if u.connected(s, t) else "no")

凸包を求めるPython3用関数を示す。

座標(x,y) は complex型データのリストで与えられるものとする。Python3では、複素数を扱うためのcomplex型がサポートされていて、以下ではreal部分をx座標、imag部分をy座標としている。

例えば、4点(0,0), (1,0), (1,1), (0,1)の座標に対応して、Python3は以下のようなリスとで表現する

a = [0, 1, 1+1j, 1j]

凸包関数のリターン値として、凸包を構成する座標のリストを反時計回りで得られる。リストの長さは座標数に対応する。

# AOJ 0068 Enclose Pins with a Rubber Band
# Python3 2018.6.22 bal4u

def cross(a, b):
	return a.real*b.imag - a.imag*b.real
	
# 凸包 入力: 座標リスト リターン:凸包を構成する座標リスト
def convex_hull(p):
	pp = sorted(p, key=lambda x:(x.imag,x.real))  # y座標を優先して昇順、同じならx座標で昇順
	n = len(pp)
	ans, j = [0]*(n+1), 0
	for i in range(n):
		while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	k = j
	for i in range(n-2, -1, -1):
		while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	return ans[0:j-1]
	
while 1:
	n = int(input())
	if n == 0: break
	p = []
	for i in range(n):
		x, y = list(map(float, input().split(',')))
		p.append(complex(x, y))
	print(n - len(convex_hull(p)))

問題文 AOJ-068 を解くためにC言語プログラムから移植したもの。

以下の例題では、ノード間に高々1本の有向道路があり、移動コストが道路に与えられている。ノードを a, b とし、有向道路のコストが a から b は c で、b から a は d としている。つまり、隣接リストとしては、to[a] = (b, c)、to[b] = (a, d) になる。

全体のノード数は V で与えられる。スタートノードは start、ゴールとなるノードは goal。

INF = 0x7fffffff
import heapq
def dijkstra(V, to, start, goal):
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for e, cost in to[s]:
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return dist[goal]

Python3では、プライオリティキュー(minキュー)の使い方は以下のとおり。

#heapq
import heapq                        # heapq のインポート
Q = []                                  # キューの作成
heapq.heappush(Q, (cost, node))     # 要素の追加
cost, node = heapq.heappop(Q)       # 要素の取り出す

Qでの要素はタプルとして定義する。タプルの最初はキーとなるもの、2番め以降は自由に追加して良さそう。

上記のダイクストラ関数を利用した例は以下に示す。AOJ-117という問題。

n = int(input())+1
to = [[] for i in range(n)]
for i in range(int(input())):
	a, b, c, d = list(map(int, input().split(',')))
	to[a].append((b, c))
	to[b].append((a, d))
s, g, V, P = list(map(int, input().split(',')))
if s == g: print(V-P)
else: print(V-P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))

ノード番号は1-indexとして入力時に与えられるので、全体のノード数を最初の行で1つ増やしておいた。

隣接リストを使って、トポロジカル・ソート(Topological Sort)をPython 3で実装する。

# AOJ 0119: Taro's Obsession
# Python3 2018.6.20

# トポロジーソート V:総ノード数, to[][]:隣接リスト
def topological_sort(V, to):
	cnt = [0]*V
	for i in range(V):
		for j in to[i]: cnt[j] += 1
	Q = []
	for i in range(V):
	   if cnt[i] == 0: Q.append(i)
	while len(Q) > 0:
		i = Q[0]
		del Q[0]
		print(i+1)  # ノードの表示
		for k in to[i]:
			cnt[k] -= 1
			if cnt[k] == 0:	Q.append(k)

m = int(input())
to = [[] for i in range(m)]
n = int(input())
for i in range(n):
	x, y = list(map(int, input().split()))
	to[x-1].append(y-1)
topological_sort(m, to)

AOJ問題119に対する解答プログラムでもある。

C言語では全く使えない正規表現がPython3では大活躍している。

使い方のメモ:

import re
pa = ">'(=+)#(=+)~$"	# A >'======#======~
pb = ">\^(Q=)+~~$"	# B >^Q=Q=Q=Q=Q=Q=Q=Q=Q=~~

for i in range(int(input())):
	s = input()
	r = re.match(pa, s)
	if r and r.group(1) == r.group(2): print('A')
	elif re.match(pb, s): print('B')
	else: print('NA')

基本的に、まずモジュール re を import することから始まる。

re.match(pattern, text) という使い方で、テキストの先頭からパターンマッチングをしていく。

テキストの途中とマッチングするならば、re.search()を使う。
re.search(pattern, text)

正規表現でマッチングした部分は r.group() で得ることができる。group(0) はマッチングした文字列全体、group(1)は最初の正規表現でマッチングした部分、group(2) は2番めの部分。

上の例題では、「#」 の前後にある「=」の数が等しいことが求められるので、group(1) == group(2) という判定条件を利用した。

C言語ならよく分かるが、Python Version 3 をはじめて勉強するひとのために、まとめておく。

自分はまさにそのひとりだからだ。

<演算子>
余り切り捨て除算: // 
  C言語でいう整数同士の除算「/」。
  実数同士の除算にも使える。 3.5//2.1 → 1.0 -3.5//2.1 → -2.0
  しかし、負数の除算ではC言語と違う計算結果によるので、要注意!!! 以下は一例。
   (Python3) -5//2 → -3
   (C言語) -5/2 → -2

べき乗: **
  C言語ではサポートされず。
  多倍長整数はPython 3ではサポートされているので、3**1000 とか平気で書ける。
  平方根なら 2**0.5。C言語のpow()関数は基本的に不要。

インクリメント演算子、デクリメント演算子はない:
  C言語の ++, — 演算子はPythonにない。i+=1, i-=1 で代用。

<データ型>
文字列 (str): a, b, c = ”, “”, str()
リスト (list): a, b = [], list()
タプル (tuple): a, b = (), tuple()
辞書 (dict): a, b = {}, dict()
複素数(complex): a, b = 2+1j, complex(2,1)
  上の5例では、変数 a, b, c はどちらも同じデータ型になる。
  文字列はシングルクォーテーション「’」で囲んでも、ダブルクォーテーション「”」で囲んでも全く同じ。

C言語でいう2次元配列のようなもの:
  arr = [[0 for c in range(200)] for r in range(100)]
  arr[99][199] = 1
  Python 3 では以上のようにリストのリストで代用する。
  グラフの連結関係を表現するのに必要な空の2次元配列は to = [[] for i in range(MAX)] で宣言する。

リストに対するソート:
  競プロではユニークな解答出力を得るために、ソート操作が欠かせない。Python3では、以下のようなコートが使える。ただし、相手が数値か文字列かによって、ソート結果が変わるので、データ型に気をつけること。たとえば、文字列”9″と”10″では、昇順が”10″, “9”になるが、数値9と10では、昇順が当然9,10になる。

tbl = [[Japan,0,5],[Egypt,1,3],[Canada,2,1],[Spain,3,7]]
for i in sorted(tbl, key=lambda x:(-x[2],x[1])): print(i[0], ',', i[2], sep='')

表示結果:

Spain,7
Japan,5
Egypt,3
Canada,1

ソートの基準:チーム名と成績を入力し、成績の良い順(勝ち点の多い順)に並べ替える。勝ち点が同点の場合は入力順に出力すること。

<リストの内包表現>
リストを簡潔に、しかも高速に生成する手法のひとつに、内包表現を利用するというものがある。Pythonに慣れないひとにはわかりにくいが。

1. for 文による内包

 a = [i for i in range(1,10)]

1から9までの連続した数値のリストが生成される。

2. for と if との組み合わせによる内包
for 繰り返しのなか、特定の要素をピックアップする。

 a = [i for i in range(10) if i & 1]

0から9までの連続した数値のうち、奇数だけを抽出してリストをつくる。

3. for と if-else との組み合わせ

 a = [i**2 if i & 1 else i**3 for i in range(10)]

0から9までの連続した数値のうち、奇数は自乗、偶数は3乗のリストをつくる(つまり、[0, 1, 8, 9, 64, 25, 216, 49, 512, 81] がつくられる)。
☆ if-else は for のまえに書かないといけないことに留意

4. 上記の if-else と for との間にネスト的に if-else を入れることができる。自己誇示、自己満足に使えそう!

print(*["fizzbuzz" if i%15==0 else "fizz" if i%3==0 else "buzz" \
if i%5==0 else i for i in range(1,2**100)], sep='\n')

C/C++プログラマは驚くしかない。

<その他>
複数変数の同時代入(初期化): a,b,c,d = 1,2,3,4
  行数節約のために、変数の初期化は上記の形で書ける。

変数同士のswap操作: a,b = b,a
  わかりやすくて便利。

<小数点の四捨五入>
以下の例は、実数 ans を小数点2桁に正確に四捨五入する。

from decimal import Decimal, ROUND_HALF_UP
ans = 9876543210.123456
print(Decimal(str(ans).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP))

max()、min()、sorted()等の関数に、keyに違う関数を指定すると、keyで指定した関数で処理される。

a = list(input().split())

# リストの中の一番長いメンバ
print(max(a, key=len))

# リストの中の一番短いメンバ
print(min(a, key=len))

# リストの中の一番頻度の多いメンバ
print(max(a, key=a.count())

# リストを長さの降順で並べる
print(*sorted(a, key=len, reverse=True))

C言語にはなかったスライス表現、慣れるととても使いやすく、簡潔な書き方が可能になる。つまり、for文を使わなくても、同等な表示が可能だ。

リストのスライス表現 a_list[start:end:step]
a_list = [1,2,3,4,5,6,7,8,9]
print(*a_list[2,-1,2]
#3, 5, 7  # 表示結果

リストaの末尾への追加 a.append(x) xがaの末尾に追加される

リストaの先頭への挿入 a.insert(0, x) xがaの先頭に挿入される。ただし、内部ではリストが移動されるので、計算時間はo(N)になるかも。

リストaからの削除 del a[offset] offsetは位置指定

リストaから取りだし、削除する a.pop(offset) offsetは位置指定、省略可(省略した場合はoffset=-1)

Python3 (Python Version 3)用のスタック実装

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

s = Stack()
while True:
    try:
        a = int(input())
        if a > 0:
            s.push(a)
        else:	
            print(s.pop())
    except EOFError:
        break

1行に整数1つの入力データはEOFになるまで与えられる。入力データが0以外のときに、データをスタックにpushする。入力データが0のときに、スタックからpopした値を標準出力する。

ビッグデータやAI等、多くのところから注目されているPython。勉強しはじめたので、少しずつまとめておきたい。

標準入力からデータを得る方法。Python 3にしか対応しないかもしれない。

1. 入力データのフォーマットは、1行だけの入力データ。ただし、その行に複数の整数がしまっている。

a = list(map(int, input().split()))

入力データがリストaに入る。

2. 入力データのフォーマットは1行に1つの整数。行数(データの数)が事前にわかる。

a = [int(input()) for i in range(10)]

入力データはリストaに格納される。データの個数はrange(n)のところで指定。

3. 入力データのフォーマットは1行に1つの整数、行数(データの数)が分からず、EOFまでとなる。

while True:
    try:
        a = int(input())
        print(a)
    except EOFError:
        break

また、同じ入力フォーマットに対して、sysを使えば、以下のようなコードでもOK。より簡潔になる。

import sys
for d in sys.stdin:
    print(sum(x**100 for x in range(int(d), 1000, int(d))))

4. 入力データのフォーマットは1行に複数の整数、行数(データの数)が分からず、EOFまでとなる。

while True:
    try:
        a = list(map(int, input().split()))
        print(len(str(a[0] + a[1])))  # 1行のデータ個数に対応して変更
    except EOFError:
        break

上の例では1行に2つのデータだが、行のデータ全体がリストaに入るので、2つ以上の複数データでも同様なコードで対応する。

それぞれの行にある複数のデータが整数ではなく、実数の場合は以下に変わる。

EPS = 0.0001
while True:
    try:
        a = list(map(float, input().split()))
        print("{0:.3f} {1:.3f}".format(a[1]/a[0]+EPS, a[2]/a[0]+EPS))
    except EOFError:
        break

EPSは実数の四捨五入誤差をなくすためのもの。試行錯誤してその値を決める。

5. 入力データのフォーマットは1行に複数の整数、行数(データの数)が入力の最初に与えられる。

n = int(input())
for i in range(n):
    a = list(map(int, input().split()))

6. 多少入力が高速になるには、以下のコードを先頭にいれるといいかもしれない。

import sys
from sys import stdin
input = stdin.readline

input()は従来とおり使ってよさそう。