競技プログラミング

Python競プロでやりがちなミス

in listでTLE

ある集合を作成した後、ある値が集合内に含まれるか調べたい時がある。

その際に、listおよびsetの計算量はそれぞれ

1
2
Key in List #  O(n) ただし、nはlistの要素数
Key in Set #  O(1)

であるので、思考停止でlistを使ってはいけない。

Pythonのsetが計算をO(1)で行えるのは、実装がハッシュテーブルであるためである。

ちなみに、listをsetに変換しようとして、

1
Set(List)

のような処理が思いつくが、この処理自体がO(n)であるので意味がない。

最大公約数・最小公倍数

1
2
3
4
# Python3.5以降
from math import gcd
# Python3.4以前
from fractions import gcd

最大公約数を求める関数を持つ標準ライブラリが、Pythonのバージョンによって異なる。

AtCoderではPython3.4.3を採用しているので、fractionsを用いる必要がある。

2020/4/13追記 Python3.8.2に更新されました

ちなみに、最小公倍数(LCM)を求める関数は実装されていないので、自前で書く必要がある。

1
2
def lcm(x, y):
    return x * y * gcd(x, y)

除算は常に浮動小数点を返す

これは割り切れるかどうかに限らない。

巨大な数を扱っている場合、浮動小数点の表現の限界に達し、計算結果が正しくならない場合がある。

一旦、誤差が出てしまうと、当然その後に整数に戻しても手遅れである。

1
2
3
4
>>> int(10 ** 22 / 2)
5000000000000000000000
>>> int(10 ** 23 / 2)
49999999999999995805696

割り切れると分かっていても、// 演算子による整数除算としておくのが無難である。

この演算は整数を返す。

1
2
>>> 10**23//2
50000000000000000000000

再帰でエラー

再帰を実装すると以下のエラーに遭遇する場合がある。

1
RecursionError: maximum recursion depth exceeded in comparison

上限がデフォルトでは1000に設定されているのでこれを引き上げる。

1
2
import sys
sys.setrecursionlimit(10**9)

10**10とかにはできないので注意。

1
OverflowError: signed integer is greater than maximum

二次元リストの宣言

イディオムとして覚える。

1
2
3
4
5
6
7
8
9
# 1次元
A = [0] * 4 # OK
# 2次元
B = [[0]*4]*4 # ダメ
C = [[0]*4 for _ in range(4)] # OK

B[0][0] = 1
C[0][0] = 1
print(A,B,C)

リストのコピー

コピー元に影響を与えずに、コピーに対して操作をしたい。

多次元ならcopy.deepcopyを使う。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import copy

a = [0]
b1 = a[:] # OK
b2 = a.copy() # OK
b3 = copy.copy(a) # OK
b4 = copy.deepcopy(a) # OK
a[0] = 1
print(b1,b2,b3,b4)

a = [[0]]
b1 = a[:] # NG
b2 = a.copy() # NG
b3 = copy.copy(a) # NG
b4 = copy.deepcopy(a) # OK
a[0][0] = 1
print(b1,b2,b3,b4)

こちらの記事を参考にさせていただきました。

PythonでTLE

PyPyで提出しましょう。

競技プログラミング コンテストのお供というコンテスト最中に使うためのチートシートも作ってみたので合わせてご覧ください！

記事情報

  • 投稿日：2020年2月11日
  • 最終更新日：2020年5月21日