ac-library-hs の Extra モジュールを作成しました

背景

AtCoder は隔年でジャッジ環境を更新しています。なんと更新時は ユーザの提案を丸ごと受け入れています から、使いたい言語やライブラリがあれば (節度を持った範囲で) 入れ放題です。いつもありがとうございます！

今回の言語アップデート に備えて作成した ac-library-hs に、 Extra モジュールを追加しました。もうじき来るであろう新ジャッジのテストに先立って、簡単に中身を紹介します。

Extra モジュールの主な内容

Extra に収録したモジュールは、概ね maspy さんのライブラリ の一部の Haskell 移植版です。金冠プレイヤー (上位 100 名の 1 人) のコードを移植したわけですから、かなり強力なモジュールもあります。かいつまんで紹介して行くので、なんだか面白そうだと感じてもらえると幸いです。

Bisect

これは僕が生み出した二分探索モジュールで、例外的に出来が悪いです。 C++ の二分探索 (lower_bound 等) を移植したつもりで、妙な API を作ってしまいました。バージョン 1.3 で修正すると思います。

Dyn*SegTree*

動的セグメント木 (必要な部分だけ作るセグメント木) のモジュールです。通常のセグメント木と比べてメモリ使用量が増え、トップダウンの畳み込みをするため効率が落ちますが、座標圧縮が必要無いなど利便性が高めです。

区間リセットや、セグメント木の部分木を別のセグメント木の部分木に差し替えるなど、変態的な操作が可能です。 Persistent 版はメモリ使用量が倍になる代わりに、永続データ構造のように操作履歴を残すことができます。使い道はよく分からないのですが (!?) 強力です。

Graph

グラフ探索のモジュールです。辞書順最小トポロジカルソート、強連結成分分解、二部グラフの着色、 block-cut tree の取得、最短経路探索 (BFS, 01-BFS, Dijkstra, Bellman–Ford, Floyd–Warshall) および経路復元を収録しています。

最短経路探索では n 次元頂点を後述の Ix0 で抽象化しているため、グリッドにも適用できます。この辺りの趣味が僕と合わないと、単にごちゃごちゃしたモジュールになります。

HashMap

Open addressing method の mutable hash map です。 Haskell では containers パッケージの永続データ型のマップを使うことが多いのですが、時として深刻な速度不足に陥ります。 この mutable な HashMap はほぼ配列並み (平均 \(O(1)\)) のスピードで動作しますから、コンテストでは心強いです。

IntMap

Int をキーとするマップです。後述の IntSet のキー毎に値を関連付けたもので、やはり高速で心強いです。 Mutable データ構造が使いやすい場合にも光ります。

IntSet

64 分木による整数集合です。 hibitset みたいなやつと言うか、 64 等分した区間毎に 1 bit の有無を表す bit 列を \(\lceil \log_{64} n \rceil\) 層持っています。おかげで Predecessor Problem (1 次元の nearest neighbor problem) が定数倍の良い \(O(\log n)\) で解けて重宝します。

IntervalMap

これは概ね 区間を管理する構造体 の写経モジュールです。区間の追加・削除を追跡しつつ、区間代入と区間削除の操作ができます。 \(q\) 回操作したとき、挿入・削除される区間の数の合計はたかだか \(5q\) 個 (のはず) ですから、区間長を \(n\) として \(O(q \log n)\) でクエリ処理ができます。

これを持っているだけで解ける問題もあります。いずれ緑 diff の典型データ構造に収束しそうです。

Ix0

これは Graph モジュールのために作った n 次元添字と添字の定義域の抽象です。 Haskell 標準の Data.Ix は閉区間を前提とするため、わざわざ半開区間・ゼロベースの型クラスを用意したわけですが、賛否両論ありそうです。

*KdTree

\(K\)-d と言いつつ 2 次元限定の静的な \(k\)-d tree です。二次元平面上で、座標軸と平行な辺を持つ矩形範囲内のモノイド積を取得できます。ただし計算量は \(\sqrt n\) らしく (解析は難しそう), 注意が必要です:

静的であり、木の構築後に点の追加はできませんが、クエリを先読みして単位元を重みとした点を木の中に入れておくことはできます。

Math

素数判定、素因数分解、約数列挙およびダブリング (binary exponentiation) を収録しています。特に整数関連の関数は、 \(n\) が非常に大きな場合も高速に動作します (計算量は確認中……) 。

Mo

区間クエリの平方分割モジュールです。クエリを上手くソートした上で、左右に伸び縮みする尺取り法のような仕組みで走査すると、 \(O((n + q) \sqrt n)\) でクエリ処理できる魔術的アルゴリズムです。

ModInt64

Montgomery 乗算による mod int です。法は奇数とします。まだベンチマークを取っていないので、色々不安です。

Monoid

主に遅延セグメント木のための作用モノイドを集めたモジュールです。区間代入、区間加算および非可換モノイドとして代表的な affine 変換があります。作用モノイド以外では rolling hash や affine 変換の対象があります。

MultiSet

HashMap をラップした multiset です。 inc / dec が \(O(1)\) で高速ですが、代わりに Predecessor Problem (1 次元の nearest neighbor problem) が解けません。思いつきで作りましたが、出番は無さそうです。

Pdsu

ポテンシャル付き Disjoin Set Union (Union-Find) です。 AtCoder 側も年々典型データ構造の幅を広げており、これを使うだけで解ける問題も幾つかあります。いずれ緑 diff 典型データ構造に収束しそうです。

Pool

内部実装用の pool です。スロットを解放すると、次の alloc 時にリサイクルしてくれます。内部実装的には、各エントリを共用体にし、空きスロットで連結リストを作るとメモリ効率が良いですが、横着して解放済みスロットの一覧を持っています。そもそも Haskell で共用体を使うのは上級者感があります。

SegTree2d

2 次元の静的な正格セグメント木です。簡単そうに響きますが、非常に取っつきにくいデータ構造でした。セグメント木の内部配列の添字の関係は \(a_i = a_{2_i} \cdot a_{2_i + 1}\) で、値の更新時にはこれを元に再帰的に配列を更新します。 2 次元添字でも同様に、ただし横方向だけではなく縦方向も更新します。

区間作用は実施できませんが、モノイド積の取得は \(O(\log h \log w)\) (のはず) なので lazy \(k\)-d tree よりも高速です。静的であり、木の作成後に点の追加はできませんが、クエリを先読みして単位元を重みとした点を木の中に入れておくことはできます。

Seq

遅延伝播反転可能 splay tree です。内部的には木でありながら、 API としては列であることを強調するため、 Seq と命名しました。 Mutable データ構造でありながら Data.Sequence よりも遥かに遅いので、あまりおすすめできません。

Seq.Map

遅延伝播反転可能 splay tree です。 Seq をラップして map としての API を実装するため、 Map.Seq としました。 Mutable データ構造でありながら Data.Map よりも遥かに遅いので、あまりおすすめできません。

SqrtDecomposition

自分で考えた区間の平方分割のモジュールです。平方分割は、長さ \(n\) の区間を長さ \(\sqrt n\) 程度ののブロックに分割し、ブロックごとに集約情報を持つことで \(O(q \sqrt n)\) 程度で区間クエリを処理するアルゴリズムです。

始めは型クラスとしての実装を考えていましたが、ユーザが必要なクエリの種類が 3 種類になる問題があったため、区間幅をブロック単位に分解するだけのモジュールとしました。遅延作用等はユーザ側で処理する必要があります。

別解として平方分割で解ける問題はそこそこありますが、実装量も実行速度も厳しくハズレ解法になりがちな印象です。始めは何でも解けるようになった気がしたものですが……。

Tree

木のモジュールです。木の直径、畳み込み、全方位木 DP (foldReroot) を収録しています。全方位木 DP で解ける問題は結構出ていて、そろそろ緑 diff になる気がしてます。

Tree.Hld, Tree.TreeMonoid

Heavy-light decomposition と、その上にセグメント木を載せたモジュールです。木をブロックに分け、頂点番号を振り直すと、頂点 (または辺) がセグメント木に載り、経路のモノイド積を \(O(\log^2 n)\) で取得できます。 LCA の取得や部分木の畳み込みも可能です。

セグメント木と比べて Fenwick Tree (binary indexed tree) がかなり速いので、そちらにも対応すべきかもしれません (maspy さんのライブラリでは対応しています) 。

Tree.Lct

弱い link/cut tree (のはず) です。辺の追加・削除ができる TreeMonoid といった趣で、とにかく強力です。部分木への作用ができると強い LCT (top tree?) になる気がします。この辺り、一部では常識のように謳われていますが、僕はついて行けません。

WaveletMatrix*

僕が作った wavelet matrix です。 maspy さんの wavelet matrix は 1 次元版でもモノイド積を取れるので、写経しておけば良かった痛恨のモジュールです。しかし早めに至らなさを実感できたおかげで、他のモジュールでは写経に徹することができました。

以上、主に写経で作ったモジュール達ですが、僕自身が完全に理解するには追加で半年必要かもしれません。人生が、人生が終わってしまう……

まとめ

ac-library-hs の Extra モジュールを作成しました。 Haskell では貴重な mutable データ構造を追加した他、 AtCoder Library には無いものの定番のデータ構造と、アルゴリズム実技検定などで稀に使えそうな強力なコードを追加できました。

この半年はひたすら ac-library-hs を作っていました。正直ユーザは僕だけになる可能性が高いですが、一応誰でも使えるライブラリを用意できたのは役得でした。早くオンラインジャッジで import AtCoder.XXX を書いてみたいです。とにかく楽しみです。