ちょっとしたことで、MacBook Air(以下MBAということにする)のOSを再インストールすることになった。自分にとって、初めての経験だったので、自己メモしておく。2度とやることはないかもしれないが。

ますは機種の確認。購入時期は平成23年1月、CPU Intel Core 2 Duo 1.6GHz、メモリ4GB 1067MHz DDR3(基板への直付けとのことのようで、交換できないらしい)、ストレージ120GB SSD SATA、英語キーボード。ACアダプターは電圧14.5V/3.1A(45W)。機種は MacBook air 11インチ Late 2010 と呼ばれるようだ。

プロキシ接続なしのネット環境下で、MBAを起動し、速やかにキー Shift+Option+Command+Rを、回転する地球儀が表示されるまで押し続ける。

数十分のダウンロードタイムを経て、やっとインストール画面が表示される。内蔵のSSDディスクの内容を消去して、OSをインストールする。OSのバージョンはMAC OSX 10.7 Lion。Apple ID、パスワードを入力したら、他のMACデバイス(自分の場合はiPhone)に6桁の認証コードが表示される。この6桁のコードをもう一度MBAにて、パスワードの後に入力して、Apple IDとパスワードの入力を完了させる(ということで、2回の入力になる。1回目はふつうのパスワード、2回目はパスワード+6桁認証コード。)

OS Lionのインストールが完了したら、MBAが使えるようになる。そこで、ソフトAppストアを起動し、購入履歴から、OSX Yosemiteにアップデートしていく。失敗談として書いておきたいのは、LionのつぎにいきなりOSX 10.11 El Capitanをアップデートしてみたところ、見事にインストール不可を食らった。数十分のダウンロード+数十分のインストールの最後にそういう表示が出てしまい、アップル社の技術なさを恨んでしまった。結局、もう一度最初から、Lionの再インストールからやり直した。

そういうことで、Lion → Yosemite → El CapitanとひとつひとつOSをアップデートしていく。所要時間は数時間以上。急ぐ場合にやれることではない。

細かい説明を省略する。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した値を標準出力する。