AtCoder2023年言語アップデートでPythonに入るライブラリ

それぞれ、何するやつかくらいのざっくり理解なので、あまり詳細なことは書いてない。

今後、使ってみて追記することがあるかも。

• Optimization with PuLP — PuLP 2.7.0 documentation

線形問題(LP)ソルバー。COIN-ORという非営利の教育財団によって開発され、オープンソースで利用できるライブラリの1つ。

Pythonでも、PyPyでも使えるようになる。

• 最適化におけるPython（PuLP版） - Qiita

変数 $x_1,x_2,...$ があり、いくつかの変数間の制約条件の下、目的関数の値を最大化（最小化）したい。
またその時の各変数の値を知りたい。という問題を解いてくれる。

• 例: ナップサック問題
  • 変数: $x_1,x_2,...,x_N$ 各品物を選ぶか選ばないかの0-1値
  • 目的関数: $x_1v_1+x_2v_2+...+x_Nv_N$ の最大化
  • 制約: $x_1w_1+x_2w_2+...+x_Nw_N \le W$

こういう条件を与えると、解いてくれる。

時間を計測すると、$N=20000,W=1000$ という $NW \simeq 2 \times 10^7$ の問題でも、手元の環境で0.6秒以下で解ける。

また、（中でどうやってるのかよく分かってないが）$W=10^9,Vの最大値10$ みたいな、一般に $V$ をキーにする方の制約でも、0コンマ何秒で解ける。

$N$ をこれ以上増やすと、さすがに2秒以上かかってくるようになる（$N=2 \times 10^5$ で、6秒くらい）。

かなり強力な武器であることは間違いないが、 使いこなすには「線形問題に上手く言い換える能力」と「それが計算量的に間に合うことが示せる能力or感覚」が必要そう。

コード例

import numpy as np
from pulp import LpProblem, LpMaximize, LpVariable, LpBinary, lpDot, value

N = 20000
W = 1000

www = np.random.randint(1, 1000, N)
vvv = np.random.randint(1, 10 ** 9, N)

obj = LpProblem(sense=LpMaximize)

# 変数の定義
x = [LpVariable(f"x_{i}", cat=LpBinary) for i in range(N)]

# 目的関数（等号や不等号などが含まれない式を obj に追加すると、目的関数となる）
obj += lpDot(vvv, x)

# 制約（等号や不等号を含めた形式を obj に追加すると、制約となる）
obj += lpDot(www, x) <= W

# 求解
obj.solve()

# 出力
print("最適値 = {}".format(obj.objective.value()))
print("最適解 = {}".format([i for i in range(N) if value(x[i])]))

答えが桁落ち?することがあるみたい。

• けむにく@競プロさんはTwitterを使っています: 「なんか死んでる https://t.co/U3v0TXOLn0」 / X

これは、↓の問題の入力例4だと思われ、

• B - 花束

“Objective Value” では正しい値が表示されているのに、それを取り出した途端、末尾2桁が00になってしまっている。
（自環境でも再現）

厳密解が求められる場面ではイマイチ信用ならんなぁ。有効桁数の設定はあるんだろうか。

Googleが作った、数理最適化ツール。分野はPuLPと似てる。

• OR-Tools  |  Google for Developers
• Googleの数理最適化ツールOR-Toolsを使ってみる - Qiita
• 第6回：OR-Toolsで巡回セールスマン問題を解く ～京都弾丸観光ツアーの作成を事例に～【ブレインパッドの数理最適化ブログ】 - Platinum Data Blog by BrainPad

Microsoftが作った、SMTソルバー。

• PythonでSMTソルバ (z3py) 入門
• Pythonで論理式を簡単に解くSATソルバー/SMTソルバーZ3の基本的な使い方まとめ
• SAT/SMTソルバの仕組み

2-SATなどの「SAT」は、SATisfiability problem、充足可能性問題のこと。真偽値が複数あって、制約を満たす解を解く問題。

一方「SMT」は、Satisfiability Modulo Theories、真偽値だけで無く数値や、もっと複雑な式が変数であっても解ける、らしい。

なんか、シンプルな使い方を見てたら「変数の制約を与えて解かせる」という流れやその用途は 線形問題ソルバと似てそうだが、違いはあるんだろうか。あまり区別できてない。

C++でいうstd::setとかstd::multisetとかが使えるようになる。速度も十分っぽい。

• Python Sorted Containers — Sorted Containers 2.4.0 documentation

• SortedSet
• SortedList
• SortedDict

SortedSetは要素の重複なし。SortedListは重複あり。

主な機能

• addで入れて、discardで消す
• bisect_left(x), bisect_right(x) で、$x$ 以上/より大きい要素位置 $O(\log{N})$
• irange(l,r) で、$l$ から $r$ までを昇順にイテレート
• SortedSetは、通常のsetよろしくdifference, intersection, union などもできる。（計算量的は不明）

任意精度浮動小数点演算ができる。

• Python/Numpyの任意精度演算(mpmath/gmpy2使用) | tm23forest.com

上記のサイトによると、mpmathは'gmpy'というC実装の多倍長ライブラリがインストールされていれば使い、高速になる。
AtCoderでは、Pythonの方にはgmpy2が入っていてmpmathによって認識もされているが、PyPyの方には入っていない。
ひょっとするとこれを使う場合はPythonの方が高速になる場合もあり得る？

演算誤差に気をつけたり、それを避けるために工夫して解かなければならない問題もたまにあるが、それらを力業で突破してしまえるかも。

• More Itertools — more-itertools 10.1.0 documentation

標準ライブラリ itertools から発展し、更にいろいろできるようにしたやつ。

リストから $k$ 個ずつひとまとめにイテレートする chunked とか、ちょこっと役立つものが何個かある。

• GitHub - not522/ac-library-python

C++ のAtCoderLibraryの移植版。

これまでも、ローカル環境にインストールして使って、提出時には結合したコードを生成する、という使い方はできたが、 結合が必要なく、直接 import atcoder できるようになった。

PythonとC++ を連携させる。

• GitHub - wlav/cppyy

以前もそういうパッケージはあったが、従来のものと比較していろいろ楽にできるらしい。

Python内にcppコードを書く必要があるが、C++でmultisetやconvolutionを実装して呼ぶと、 sortedcontainerや、ACLのconvolutionより高速に動作した例もある。

• rikeinさんはTwitterを使っています: 「諸々解決したので、cppyyでwrapしたmultisetによってABC170E, ABC212Dを解くコードが、新ジャッジで動作することを確認しました。compile phaseでcompileを実施する仕組み付きです。コードはこちらhttps://t.co/HwR76pUFDA 比較用にsortedcontainersで解くコードも載せています。 https://t.co/MbEI6AHcd6」 / X

01で表されるbit配列を、シフトしたり、XORしたりする。

64bit程度までなら整数をbit配列的に扱って問題ないと思うが、それ以上になるとこっちの方が有利だったりするのだろうか。

機械学習。AHC用途かな。

どちらも、2次元テーブル的なデータを扱う、データ分析用ライブラリ。

• pandas - Python Data Analysis Library
• Polars User Guide

アルゴリズムではあまり使わなさそう…。ヒューリスティックの開発に、人によっては使うことがある？

• The Shapely User Manual — Shapely 2.0.1 documentation

幾何的な概念を扱うライブラリ。

頂点の座標を与えてポリゴンの面積計算をするなど、幾何問題で楽になりそうな機能はあるが、計算時間がどの程度になるかは未調査。

PyPyでも使えるようになった。ただし、以下の点に留意が必要。

• importに400msくらいかかる
  • rikeinさんはTwitterを使っています: 「というか、PyPyのnumpyのimportオーバーヘッドも割とひどいですね（CPythonの6倍程度です）。以前どうだったかはデータを残していないので不明ですが。 https://t.co/N08ozooNEu」 / Twitter
• Numpyで計算する箇所の速度は、素Python上のNumpyと比較して速いわけではない。というかむしろちょっと遅い?
  • 新judgeコンテストのコードテスト上で実行
  • 100×100行列を2つ生成して内積をとる操作を1000回
    • Python: 697ms
    • PyPy: 872ms
  • $10^5$ 要素の1次元配列を2つ生成して、np.rfftで畳み込む操作を50回
    • Python: 2454ms
    • PyPy: 2656ms

特に、400msのオーバーヘッドはなかなかきつい。
「Numpyは一部利用するが、他にもPython上で実行される重いコードがそれなりにあり、その部分をPythonからPyPyにした時の高速化が400msを上回る」というような場合以外 （Numpy上の演算メインの解法とか）は、従来通りPythonで提出した方がよさそう。

内積テストコード

import timeit
import numpy as np


def test():
    a = np.random.randint(0, 1000, size=(100, 100))
    b = np.random.randint(0, 1000, size=(100, 100))
    c = a @ b
    return c[0, 0]


result = timeit.timeit('test()', globals=globals(), number=1000)
print(result)

# Python : 0.6966993230162188
# PyPy   : 0.8724668700015172

畳み込みテストコード

import timeit
import numpy as np


def convolve(f, g):
    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1

    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:true_len]


def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)

    a = convolve(f1, g1) % p
    c = convolve(f2, g2) % p
    b = (convolve(f1 + f2, g1 + g2) - (a + c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p


def test():
    a = np.random.randint(0, 1000, size=100000)
    b = np.random.randint(0, 1000, size=100000)
    c = convolve_mod(a, b, 998244353)
    return c[0]


result = timeit.timeit('test()', globals=globals(), number=50)
print(result)

# Python : 2.454356900998391
# PyPy   : 2.6560454019345343