はじめまして。
先週競プロに入門した初心者です。
今はpythonを使っています。
出来ればC++に頼ることなく競プロで良い結果を出したい！
ということでpythonのままスコアを上げる方法を考えました。
例えばC++では
#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
こんな感じで高速化をする人が多いです。
要するに、頻繁に使う記述を簡略化しておくって感じですかね。
前からこういうおまじない的な慣習があることは知っていました。
が、これのpythonバージョンはpythonで競プロをやっているのに知りません。
そこで、pythonの競プロ強者の慣習を学んでいこうと思い、この記事を書きました。
同じような方にも参考になれば幸いです。
はじめにしたこと
強い人の提出コードを読みました。
やっぱりC++競プロと同じようなおまじないがあったので解読していこうと思います。
(とある強そうな人から引用しています)
実際のコード
実際のコードを順に説明していく。
sys.setrecursionlimit(10 ** 6)
再帰関数の再帰の深さを設定する。(defaultは1000)
意味はわかるが必要性がピンとこない。
調べてみたところ、これで引っかかる場合もあるらしく、とりあえず大きめに設定するという感じ。
確かに、これが原因でエラーが出た時、気付くの難しそう。
次に、こんなものも見つけた。
int1 = lambda x: int(x) - 1
入力した数字に1を引いたものを返す関数。
ここまでするのか、、、競プロ強い人の執念を感じる笑
出力関連
p2D = lambda x: print(*x, sep="\n")
リストの要素を改行を挟んで表示する関数。
確かに、この前Atcoderやった時も、これがあると良い場面があった笑
入力関連
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
初心者の私はinput()ばかり使っていたので、まずreadline()との違いを整理する
- readline()は末尾の改行文字も読み取る
- input()は読み取った改行文字を消してくれる(つまりreadline().rstrip()と同値)
ただ、int('1\n')=1なので、このように記述できる。
引用先の人はこのようにreadline()を使っているが、input()でも代用できそう。
よく使われるライブラリ
次に、頻繁に使われているライブラリを洗い出してみました。
配列関連
pythonは配列のpop,appendが遅いので、実行時間で不正解となる場合は以下のように記述してデック（両端キュー）を使う。
from collections import deque
l = deque
l.append(1)
l.pop()
次に配列を複製する際の話
# 配列が1次元の場合
list2 = list1[:]
# 2次元以上の場合
import copy
list2 = copy.deepcopy(list1)
1次元の場合、「list2=list1」とすると参照渡しのせいで、list2自体を書き換えてしまうとlist1も書き換えられるので、このように記述する。
2次元以上の場合は、このように記述できないのでdeepcopyを使う。
データ構造
競プロにおいてヒープ(プライオリティーキュー)を使うことは多い。(中央値を求める場合とか)
ヒープは次のような性質を持つ
- 要素の追加(push)、除去(pop)がO(logN)の時間で出来る
- 最小値(最大値)探索がO(1)で出来る
最小値が頂点にくるような仕様になっているため、最大値を頂点に持っていきたい場合は-1を掛けてヒープに保存すれば良い。
以下のようにしてヒープを扱える。
import heapq
heap = []
heapq.heappush(heap, 1)
heapq.heappop(heap)
辞書
pythonで通常の辞書を使う場合、キーに対応するバリューが存在しているか確認する必要がある。
そのような手間を省いてくれるのがdefaultdictである。
(競プロとかでなくとも使う場面が多い気がする)
以下のように使う
from collections import defaultdict
d = defaultdict(int)
# キーがない場合のデフォルトを設定する場合、このように記述
d = defaultdict(lambda : 'Initial Value')
まとめ
ざっくりこのくらいかと思うが、まだまだ足りないところも多いと思うので、随時更新していく予定。
こういう知識がいつか実務でも役に立つと信じて学習も続けていこうと思う。