atcoder新ジャッジのpypy3.10で入っているライブラリたちを確認

初めに

ABC314以降ジャッジが更新されていて、各言語がアップデートされています。
pypyも3.10にバージョンが上がりライブラリも増えたので調べた内容を残しておきます。
今後また調べたら追記します

ライブラリ一覧

numpy==1.24.1
scipy==1.10.1
networkx==3.0
sympy==1.11.1
sortedcontainers==2.4.0
more-itertools==9.0.0
shapely==2.0.0
bitarray==2.6.2
PuLP==2.7.0
mpmath==1.2.1
pandas==1.5.2
z3-solver==4.12.1.0
scikit-learn==1.3.0
ac-library-python
cppyy==2.4.1

参考： https://img.atcoder.jp/file/language-update/language-list.html

numpy

pythonと言えばこれという人も多いと思うが今までpypyでは使えなかった
諸々高速だと思うのでnumpyを使えば重い想定解法が通りやすくなるはず
行列への演算をしたいときにも便利

scipy

数値計算用のツール群
combinationとかの計算で使う可能性がある程度

networkx

使わない→importのみで300msかかっておっそい
https://qiita.com/yH3PO4/items/ffd81081c254895939c0
時間の制約的に使える操作が限られてるから覚えたら特定の操作の時のみ楽になりそう

sympy

方程式解いてくれそうだけど使う機会分かりません

sortedcontainers

普通に便利そう
std::multiset 相当なはずの SortedList ではadd,pop,clear,remove,discard,bisect_left,bisect_right,count,indexなどの関数がある、とりあえずadd,popさえできればそれだけで便利
https://grantjenks.com/docs/sortedcontainers/sortedlist.html
簡単な使い方

以下が800ms計算量はNlogNだと思うけど十分高速
先頭要素を表示するとheapqでいいじゃんとなるので小さいほうから5個目を表示している

from sortedcontainers import SortedList
import random
sl = SortedList()
N=10**6
for i in range(N):
  sl.add(random.randint(1,N))
  if len(sl)>5:
    print(sl[4])

more-itertools

いろいろあるけど大抵自前でもできる、使えば虚無な部分がある程度楽になりそう

from more_itertools import chunked, split_at,unzip,seekable,run_length

# 2個ずつのリストを返す
print(*chunked([1,2,3,4,5],2)) # [[1,2],[3,4],[5]]

# 対象要素を削除して分割、削除しないsplite_before,split_afterやsplit_whenもある
print(*split_at([1,2,3,4,3,5],lambda x:x==3)) # [[1,2],[4],[5]]

# unzip zipの逆
x,y=unzip([[1,2],[3,4]])
print(list(x),list(y)) # [1,3] [2,4]

# 

# seekできるiterator初めて3に出会ったときにseekでループを巻き戻す
# 少し戻らなきゃいけないタイプの特殊ループにつかえそうではある
l=[1,2,3,4,5]
x=seekable(l)
flg=False
for v in x:
  print(v,end=",") # 1,2,3,1,2,3,4,5,
  if not flg and v==3:
    flg=True
    x.seek(0)  
print()

# ランレングス　encode,decode
l=[1,1,2,3,4,4,5]
print(*run_length.encode(l)) # (1, 2) (2, 1) (3, 1) (4, 2) (5, 1)
l=[(1,2),(3,5),(4,1)]
print(*run_length.decode(l)) # 1 1 3 3 3 3 3 4

shapely

平面幾何学オブジェクトの操作と分析のためのパッケージ
平面操作ができるかも、詳しく調べておらず

bitarray

C++でいうbitsetか、大量のbitを効率的に扱う場合に使うよう

PuLP

以下のような問題が解ける、もっと解けると思うができることの範囲と計算量を見積もる方法はわからない
https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0

材料AとBから合成できる化学製品XとYをたくさん作成したい。
Xを1kg作るのに、Aが1kg、Bが3kg必要である。
Yを1kg作るのに、Aが2kg、Bが1kg必要である。
また、XもYも1kg当りの価格は100円である。
材料Aは16kg、Bは18kgしかないときに、XとYの価格の合計が最大になるようにするには、
XとYをどれだけ作成すればよいか求めよ。

mpmath

mp.dpsを15(default)にしておけば普通のfloatと同精度
実行時間を正しく見積もれば誤差問題を簡単に突破できる可能性を秘めている
実行時間ギリギリになるようdps設定したうえでWAだった場合に悲しくなりそう

from mpmath import mp,pi,sin
mp.dps = 50 # 10進数50桁の精度で計算
print(sin(pi/3))
# atan,log,sin,sqrtなどいろいろあるので必要に応じてググれば使えそう

pandas

データ解析を容易にする機能を提供するPythonのデータ解析ライブラリ
AHCでは使うだろうか、あまりアルゴの方で役に立つイメージはなし

z3-solver

sat-solverっぽい、自分のレベルだとあまり出ないので充足可能性問題に出会ったときに考える

ac-library-python

競技プログラミングをするフレンズさんが言及していた
https://twitter.com/kyopro_friends/status/1691768718102262074

ac-libraryのpython版、dsu(UnionFind)、LCA、最大流、最小費用流、SCC、floor_sum、lazy segmenttreeなど
dsu以外どちらかというと青、黄色以上で使うイメージ

cppyy

cppyyを使ってmultisetをwrapしている方を発見
上手に使えばC++のライブラリがうらやましくなることはなさそう
ただし、コンテスト中に書くには難易度が高そう