はじめに
AtCoderのSteak Sumも126日に達し、レートも緑になったということでAtCoder関係の記事もどんどん書いていこうと思います。AtCoderをやっているとアルゴリズムは合っていると思うのに言語仕様の問題でACできないということが多々あります。そんな初見殺し的な要素をPythonに関して紹介できたらと思います。
その１再帰上限 RecursionError
UnionFindや深さ優先探索を実装するときに起きがちなエラーです。
これは初見だとまず気がつかないと思います。
というのも問題ページのテストケースではまずこのエラーが生じることはないからです。
このサイトによると大体未設定では1000ぐらいまでしか再帰できないようになっているそうです。実際に提出してみるとReとだけ表示されて何が原因なのか自分の環境ではなかなか割り出せません。RecursionErrorが起きてます！
import sys
sys.setrecursionlimit(10000000000)
みたいな感じで再帰上限を増やしてあげましょう。
その２ 大きな桁の演算は遅い
これは有名ですね。
主に10^18とかので掛け算とかをしようとするとTLEをもらう可能性が高いです。
ただしシフト演算(<<)は桁数を増やしてもあまり遅くならないので注意が必要です。それを利用した問題がABCのE問題の過去問にあって難しかったです。
その3 モジュロ逆元
モジュロ逆元についてご存知ない方はこちらをご覧ください。
Pythonにはモジュロ逆元を求める関数を組み込みのpow関数で使用することができます。
mod = 10**9+7
pow(7, -1, mod)
と書くと
7x ≡ 1(mod 10**9+7)
となるxを求められます。
しかしこの関数AtCoderのPythonでは使えるのですがPyPy3ではなぜか使えません！（なんで？）
この前の日曜日、間違えて提出してペナルティをもらい、それがなければ1000番以内になれてました。
最後に
他にも何かあると思うので、思いつき次第記事にしていこうと思います。
参考リンク
クリエイティヴなブログ ふるやんのほぼ競プロ日記 競技プログラミングにおける剰余の基礎と mod 逆元
https://www.creativ.xyz/modulo-basic/
note.nkmk.me Pythonの再帰回数の上限を確認・変更
https://note.nkmk.me/python-sys-recursionlimit/