in listでTLE
ある集合を作成した後、ある値が集合内に含まれるか調べたい時がある。
その際に、listおよびsetの計算量はそれぞれ
1 | Key in List # O(n) ただし、nはlistの要素数 |
であるので、思考停止でlistを使ってはいけない。
Pythonのsetが計算をO(1)で行えるのは、実装がハッシュテーブルであるためである。
ちなみに、listをsetに変換しようとして、
1 | Set(List) |
のような処理が思いつくが、この処理自体がO(n)であるので意味がない。
最大公約数・最小公倍数
1 | # Python3.5以降 |
最大公約数を求める関数を持つ標準ライブラリが、Pythonのバージョンによって異なる。
AtCoderではPython3.4.3を採用しているので、fractionsを用いる必要がある。
2020/4/13追記 Python3.8.2に更新されました
ちなみに、最小公倍数(LCM)を求める関数は実装されていないので、自前で書く必要がある。
1 | def lcm(x, y): |
除算は常に浮動小数点を返す
これは割り切れるかどうかに限らない。
巨大な数を扱っている場合、浮動小数点の表現の限界に達し、計算結果が正しくならない場合がある。
一旦、誤差が出てしまうと、当然その後に整数に戻しても手遅れである。
1 | 10 ** 22 / 2) int( |
割り切れると分かっていても、// 演算子による整数除算としておくのが無難である。
この演算は整数を返す。
1 | 10**23//2 |
再帰でエラー
再帰を実装すると以下のエラーに遭遇する場合がある。
1 | RecursionError: maximum recursion depth exceeded in comparison |
上限がデフォルトでは1000
に設定されているのでこれを引き上げる。
1 | import sys |
10**10
とかにはできないので注意。
1 | OverflowError: signed integer is greater than maximum |
二次元リストの宣言
イディオムとして覚える。
1 | # 1次元 |
リストのコピー
コピー元に影響を与えずに、コピーに対して操作をしたい。
多次元ならcopy.deepcopy
を使う。
1 | import copy |
こちらの記事を参考にさせていただきました。
PythonでTLE
PyPy
で提出しましょう。
競技プログラミング コンテストのお供というコンテスト最中に使うためのチートシートも作ってみたので合わせてご覧ください!
記事情報
- 投稿日:2020年2月11日
- 最終更新日:2020年5月21日