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

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に対する解答でもある。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使い方のメモ:

基本的に、まずモジュール 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になる。

表示結果:

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

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

1. for 文による内包

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

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

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

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

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

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

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

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

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

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

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

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

リスト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)用のスタック実装

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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