読者です 読者をやめる 読者になる 読者になる

Pythonで競技プログラミング

ありがたいことにAOJもAtCoderもいろいろな言語に対応しています. 邪道な感じですが新しい発見があっておもしろいです.

入力

C/C++/Javaから始めるとraw_inputもinputも1行とってくるので一瞬つまります. raw_inputをsplitしましょう.カンマ区切りも柔軟にいけます.

ただし,このままでは文字列のリストなので変換しましょう. forの内包表記でも良いですが,map関数を使うと便利です.

map()が便利です. 各要素を,それ自身を引数にした関数の戻り値で置き換えてくれます.

#!python
x, y = map(int, raw_input().split())

これなら関数をちょっと工夫するだけでいろいろできます.

あと,

#!C++
while (cin >> x >> y, x || y) 

の代用はあるのかな.

#!python
while True:
    x, y = map(int, raw_input().split())
    if x == y == 0: break

みたいに書くしか無いような気がするんですが…

EOFまでってのもちょっと悩みます.

入力が1行で完結するなら

#!python
import sys
for line in sys.stdin:
    line.split()

と書けます.

1行で完結しない場合はEOFErrorをexceptするしか無いのかな…?

heapq

priority_queueの代替にheapqを使います. tupleを入れればpairのpairのpairとかは使わなくてよいのでその点は良いのですが,que.top()とか書きたいですね.

一応,Queue.PriorityQueueはありますが,マルチスレッドサポートのためのロックがあるので競技プログラミング向けでは無いでしょう.

bisect

binary_searchやlower_boundとかの代替はコレになります. Pythonのリストはvectorと似ているので,挿入はO(n)です.

また,APIドキュメントの例は普段C++で解いている人にも役立つでしょう.

itrtools

効率的なアルゴリズムが思いつかない人の味方です(笑). 全探索が有効な問題であれば役に立つ機会があるのではないでしょうか…

random

問題を解く上では役立ちませんが(乱択を除く),適当な入力を作るのに役立つでしょう. assertと組み合わせて提出前の確認に利用できます.

curses.ascii

ctype.hの代替