プログラミング-競技プログラミング
尺取法ライブラリ 尺取法のPythonライブラリです。英語でTwo Pointersっていうらしいです。 数列のうち、ある条件を満たす部分数列を数え上げたり、最大の長さの部分数列を求めたりすることができます。 from copy import deepcopy from operator import add…
Imos法ライブラリ imos法のPythonライブラリです。 imos法はあるの区間に対して処理を行うクエリがたくさん与えられるときに使うアルゴリズムです。詳しくはいもすさんによる解説記事を見てください。 from itertools import accumulate class Imos: def __i…
二部探索ライブラリ 二部探索をしてくれるPythonライブラリです。 Pythonのbisectモジュールはソートされたリストにしか対応しておらず、単調増加関数に対する二部探索は自分で書く必要があります。 以前のものより小回りが利くようにクラスモジュールで定義…
階乗・順列・二項係数の剰余を求めるライブラリ 競プロでよく使うやつをライブラリ化しました。Moduloが素数でない時は上手く動きません。 class Factorial(): def __init__(self, mod=10**9 + 7): self.mod = mod self._factorial = [1] self._size = 1 sel…
JupyterLabとは JupyterLabは、Project Jupyterで次世代のWebベースのユーザーインターフェイスです。Jupyter notebookの後継として開発され、データサイエンティストの界隈では有名なアプリケーションです。ざっくりとPythonのIDEみたいな使い方ができます…
グリッド用ライブラリ 競プロでグリッド系の問題が出てとき、手間取りがちなのでライブラリにまとめました。 numpy実装でnumpy特有のスライスも対応してます。 np.allやnp.whereなどndarrayを引数にする関数を使いたい場合は、Grid.gridをお使いください() i…
追記(2020/07/15) 二部探索用コードはアップデートされました。 ⇨更新先サイト 二部探索デコレータ関数 二部探索用のPythonコードのメモ書きです。 デコレータを使っていい感じにしてます。 def bisect_search(l=0, r=10**6): def _bisect_search(f, l=l, …