まえがき
競プロで使えるPythonの小技をまとめてみました。定数倍は遅いものも多いかも。
他のテクニックなども教えてください。追加します。
再帰
PyPy、Pythonだと再帰が遅いのは周知の事実(そうか？)だと思います。
ですが、Cythonだと再帰が割と速いということはあまり知られていない気がします。PyPy、Pythonで通らない再帰DP、再帰DFSなどでもCythonでそのまま提出するだけで通ることもあるのでどうしても非再帰にするのが面倒だったりするときは試してみてもよいでしょう。
-~n
これはn+1です。それだけだとあまり使いどころが無いですが、-~nを使うとl=[0]*(n+1)の代わりにl=[0]*-~nと書くことができます。かっこを書く時間が無くなって少しコーディングの速度が上がるかもしれません。
追記~n単体だと-n-1を意味するのでリストの後ろから見るときなどにl[~i]と書くとl[-i-1]と書くより少し楽になります。
list[-1]を活用する
累積和、DPなどを1-indexedで書いている人はいませんか？書くものによって1-indexedか0-indexedかを変えるとバグが発生しやすくなり、可読性も低くなってしまいます。
Pythonならlist[-1]でリストの最後の要素にアクセスすることができるので、無駄な条件分岐を入れずに累積和やDPを0-indexedで行うことができます。例えば、下のコードのようなことができます。
#入力
n=int(input())
l=[*map(int,input().split())]
#累積和
c=[0]*-~n#一つ多く要素を作っておく
for i in range(n):
c[i]=c[i-1]+l[i]
#アクセスするときも簡単
c[r]-c[l-1]#c[-1]は0になっている
sum(hoge for i in l)
リストの中からある条件を満たすものの個数を求めたいとき、
cnt=0
for i in l:
if i>hoge:cnt+=1
のようなことをしていませんか？このように書くと時間がかかるし、なによりエレガントではありません。代わりに、
cnt=sum(i>hoge for i in l)
と書くとエレガントかつ短いコードを書くことができます。
map(lambda x:hoge,l)の利用
リスト全体に対してある操作をしたいとき、for文を使って書くと時間がかかるし、なによりエ(以下略)
代わりに、l=[*map(lambda x:x+1,l)]のように書くとエレガントかつ短いコードを書くことができます。
print(*l,sep="hoge")
整数のリストを改行区切りで出力したいとき、for i in l:print(i)などと書く代わりに、print(*l,sep="\n")と書くことができます。"\n".join(l)だとリストの要素が文字列である必要があるので迷ったらこの技を使うとよいかもしれません。
open(0)
N M
K
A_1 A_2 ... A_N
受け取る入力がこのようなとき、
n,m=map(int,input().split())
k=int(input())
a=[*map(int,input().split())]
と書くと少し長すぎますよね。そんなときはn,m,k,*a=[*map(int,open(0).read().split())]と書くと少し短くコードを書くことができます。
hoge=huga=piyo
これは少し有名かもしれません。
複数の変数を同じ値にセットしたいとき、
a=1
b=1
c=1
のように書くとあまりエレガントではありません。a=b=c=1と書くとシンプルに書くことができます。