凸包を求める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 len(Q):
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for i in to[s]:
			e, cost = i
			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

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

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

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

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()))

311の昨日に、AOJとの愛称で呼ばれ、日本国内では有名なプログラミングオンラインジャッジシステム(Aize Online Judge)で解く問題数ランキングで3位になった。昨年の7月末に参戦し、7ヶ月半で達成した。つまり、平均して一日5問解いた計算になる。

UVaでの教訓として、今回は問題をただ解くだけでなく、なんとか各問題の計算スピードが1位になるように頑張った。0:00 秒となった解答は提出された時間順で並べられ、それ以上の順位に食い込むことはできないが、それ以外の問題についてはチャレンジチャンスはいくらでもあるから。

ほぼC言語一本で解いてきたので、C++やJAVAに比べて不利な面は否定できない。ただ、C言語の自由度、スピード性は21世紀の今日になってもその特徴は生きているところも事実だと再認識した。

1位になるか。未解答問題の多くは難しく、ここからさらに1位との差である116問を解くのに大きな山はいくつもあると思うが、根性という点では誰にも負けないことを期待しよう。

昔のUVa時代と違って、競技プログラミングの重要性は広く認知されているし、アルゴリズムの素晴らしさに感動したひとも多くなった。小中学校生のプログラミング必修化は競技プログラミング愛好家にとっても喜ばしい状況ではある。

そういえば、UVaも最高3位(2006年11月21日に達成)だった。その成績は日本からの挑戦者記録としていまも生きている。

ブログシステムを MovableType から WordPress に移行したものの、写真の扱いが一部変わったので、その修正作業に追われた。

ひとつは MovableType で活用した Lightbox というプラグインの移行問題。Lightbox を導入すると、小さいサイズ(アイキャッチ画像)の写真を記事に埋め込み、そこをクリックすると写真が元サイズで大きく拡大表示される。記事の横幅が600ドットとか制限があるため、サイズがそれ以上の写真を見せるには、Lightbox が必要だったわけだ。

アイキャッチ画像の作成はLightboxによって自動的に作成される。縮小したいサイズを指示するだけでOK。

できあがったhtmlコードは一例として、以下のようになっている。

<a rel="lightbox" href="/hobby/img/
130525-8.png">
<img alt="130525-8.png"
src="/hobby/assets_c/2013/05/
130525-8-thumb-510x486-1487.png"
class="mt-image-center" style="text-align: center; display: block;
margin: 0 auto 20px;" height="486" width="510" /></a>

しかし、このままでは WP に移行しても画像は表示されない。代わりに、ファイル名の表示があって、そこをクリックしてはじめて画像が表示される。致命的エラーにはならないが、改善したい。

試しに、WP では以下のように直すと画像が難なく表示される。

<a href="/hobby/img/130525-8.png">
<img alt="130525-8.png"
src="/hobby/img/130525-8.png"
class="mt-image-center" style="text-align: center; display: block;
margin: 0 auto 20px;" height="486" width="510" /></a>

整理すると、修正箇所は以下の3点。

  1. rel=”lightbox” を削除
  2. assets_c/2013/05 を img に置き換え
  3. -thumb-510×486-1487 を削除

手動でやるのであれば、時間がかかるが、いつかは修正が終わる。ただ、記事の数が2500、一つの記事に画像が複数の場合も結構ある。ということで、自動修正を試みた。

wp での記事一括修正プラグインとして、Search Regex が有名。何しろ、正規表現が使えるから。しかし、ネットで調べても、earch Regex の正規表現をまともに説明するところはあまりにも少ない。ゴミ記事のオンパレードだからね、ネットは。

最終的に、トライアンドテストで以下のように使うことにした。結果オーケー。

  1. rel=”lightbox” の削除。
    正規表現は必要なく、ヌル文字で置き換えれば済む。
  2. assets_c/2013/05 の置換。
    正規表現
    Search pattern: #assets_c/\d+/\d+#
    Replace pattern; img
  3. -thumb-510×486-1487 の削除。
    正規表現
    Search pattern: #-thumb-\d+x\d+-\d+.#
    Replace pattern: .

また、上の例と関係ないが、Search pattern に ( ) をつけることによって、その部分を Replace pattern で再利用することもできる。

Search pattern: #daily/img/([\d]+)-([\d]+)-([\d]+).html#
Replace pattern: daily/img/$1-$2.jpg
Result: daily/img/12-3456-789.html → daily/img/12-3456.jpg

Search pattern: #hobby/img/([\d]+)-([\d]+).html#
Replace pattern: hobby/img/$1.jpg
Result: hobby/img/1234-789.html → hobby/img/1234.jpg