AtCoder Python 謎テク集

AtCoderで使える、Pythonを使って色んなことをするテクニック集です。謎テクといいつつ結構役に立つと思います。
AtCoder以外のコンテストサイトでは、こういう技が禁止されてたりするので、利用規約やらを読みましょう

逐次更新していきます　乗ってなくてなんかいい感じのあったら教えてください

CPython

CPythonで使える技です

コンパイル時計算(?)

C++などのコンパイル言語では実行をする前にコンパイルをするフェーズが必要ですが、CPythonでは、実際の実行をする前にコンパイルフェーズ的な実行が1回されます。コンパイルフェーズと実際の実行は実行環境を共有するので、コンパイルフェーズで作ったファイルを実行時に参照したりできます。そのため、前計算、ライブラリの展開、コンパイルなどといった時間のかかる処理を事前にしておくことができます。

このコンパイルフェーズはおそらくCPython固有で、他のスクリプト言語やPython処理系(PyPyなど)にも存在しません。CPythonの初回実行が遅くなる現象に対処するためこうなっているっぽいです。
これはいろんなテクニックの基礎になっています。

import sys
import os


if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    pass  # コンパイルフェーズ

# ランタイム

sys.argv[-1] == "ONLINE_JUDGE" はコンパイルフェーズであること、 os.getcwd() != "/imojudge/sandbox" は実行がローカルでされていることを意味します。

CppSet(平衡二分木)

CPythonは当然C言語のインタプリタで動作していて、C言語やC++で実装したライブラリを使うことができます。それを利用して、GCC拡張の平衡二分木をPythonから利用できるようなライブラリを作ることができます。

Pythonの公式ドキュメントにはこういったライブラリの書き方が書いていますが、詳しくない人が書けるほど簡単でもないので先人の知恵を利用しましょう。僕がいつもお世話になっているLgeuさんのライブラリを載せておきます。

リポジトリ: https://github.com/Lgeu/snippet/blob/master/cpp_extension/wrap_cpp_set.py
ブログ: https://nagiss.hateblo.jp/entry/2020/09/08/203701
IDEとかで補完されるようにしたバージョン: https://github.com/nahco314/nalib/blob/main/library_py/cset/wrap_cset.py

例: ABC217-D
CPython(AC): https://atcoder.jp/contests/abc217/submissions/32585035

Cython(with C++)

Cythonというものがあります。簡単に言うと、かなりPythonに近い言語(Pythonの方言)で、PythonとC(C++)の両方とやりとりできる言語です。詳しくは調べてください。

AtCoderの言語欄にはCythonがありますが、これはC言語の機能しか使えないもので、vectorなどのC++の基本的な機能が使えません。
これを解決するために、ソースコードに実行したいCythonコードを埋め込んだ上でPythonのコンパイルフェーズでC++を使えるようにコンパイルするという方法があります。

PythonからC++のCythonを呼び出せると、vectorや(平衡二分木による)setを扱える上に、適切な型注釈を入れるとC++レベルの速度に高速化することができます。
詳しくはこの記事を見てください: https://qiita.com/Chippppp/items/d20303f79342cb9c2423

例: ABC189-C
CPython(TLE): https://atcoder.jp/contests/abc189/submissions/32584675
Cython(AC): https://atcoder.jp/contests/abc189/submissions/32585461

numba

numbaはPython関数をJITコンパイルすることで高速化するライブラリです。

コンパイルするためには割と気を遣ってコードを書く必要がありますが(対応してない言語機能が多い)、コンパイルできると限界高速化したC++以上に高速だと思われます(肌感)。ちなみに、numpyと併用することが想定されてるっぽいですが、競プロじゃnumpyなんて使いません(人によりますが)

numbaはサードパーティーライブラリなのでインストールする必要がありますが、AtCoderのCPythonにはインストールされているので使えます。JITコンパイルはその名の通り実行時にコンパイルするので500msぐらいのオーバーヘッドがありかなり痛いですが、それでもめちゃくちゃ高速化になるので有用です。
事前にコンパイルしておくAOTなんかもあって、場合によっては使えるかもしれません

例: ABC189-C
CPython(TLE): https://atcoder.jp/contests/abc189/submissions/32584675
CPython with numba(AC): https://atcoder.jp/contests/abc189/submissions/32584667

PyPy

PyPyで使える技です

SortedContainers

Pythonで実装された、Sortedなコンテナのライブラリです。これらはC++でいうsetやmapに対応するようなことができます(k番目の値をO(log N)で取得など)。
CPythonだと多分遅すぎて使い物になりませんが、PyPyだとそこそこ使えます。
オープンソースでGitHubに公開されているので適当に引っ張って来ましょう。
リポジトリ: https://github.com/grantjenks/python-sortedcontainers

例: ABC217-D
PyPy(with SortedContainers): https://atcoder.jp/contests/abc217/submissions/32585589

CppSet,Cython

CPythonの欄で紹介したCppSetやCythonは、実はPyPyでも使えます。C(C++)で動作するこれらはPythonでインタプリタが書かれたPyPyでは動かなそうですが、(読んでないので詳しいことはわかりませんが)PyPyのインタプリタはC(C++)で書かれたPython用ライブラリをエミュレートする機能があるらしく、使えます。

なお、PyPyで動かすためにはCPythonでコンパイルしてはいけないのですが(CPython向けのバイナリが生成されてしまうため)、AtCoderのPyPyにはCythonライブラリがインストールされていません。また、AtCoderのPyPyはバイナリしかなく、C(C++)で書かれたライブラリを実行するためのincludeディレクトリが存在しません。そのため、PyPyのincludeディレクトリをテキストとして提出コードに埋め込んでコンパイルフェーズに展開、それをgccに渡し直接バイナリを生成するという手段を取っています。

具体的な使い方は、僕のライブラリを使い、USE_PYPYをTrueして、CPythonで提出するだけです。CPythonからPyPyを呼び出すため200msほどのオーバーヘッドがある上、あくまでエミュレートしてるだけなのでCPythonから呼ぶCythonほど早くないですが、割と使えます。

ライブラリ(CppSet): https://github.com/nahco314/nalib/blob/main/library_py/cset/wrap_cset.py
ライブラリ(Cython): https://github.com/nahco314/nalib/blob/main/cython/cython_by_pypy.py

例: ABC189-C
Python with Cython (AC): https://atcoder.jp/contests/abc189/submissions/32585461
PyPy with Cython (AC): https://atcoder.jp/contests/abc189/submissions/32585792