Zenn
Open20

Library Checker をやるぞ！

AtCoder
toyboot4etoyboot4e

ローカル環境で verify するには (Haskell)

verifycation-helper (oj) を使うとローカルで verify できます。 Haskell のデフォルトの実行コマンドは runghc のため、コンパイル実行には追加設定が必要です。

toyboot4etoyboot4e

Sample

入出力の高速化を図ります。

A + B

これは本当にサンプルでした。

main=interact$show.sum.map read.words

Many A + B

291 ms. String 縛りだと TLE になるため bytestring パッケージを導入します。

入力を速くするためには、どうしても ByteString の内部に触れる必要があります。 Unboxed tuples の嵐になるため飛ばしています。

出力には ByteStringBuilder が効きます。中身は LazyByteString の連結リスト (?) で、バッファを経由せずに直接 stdout に書き込まれるようです。正格な ByteString を結合していくと O(N^2) になりますが、 ByteStringBuilder の結合は O(N) で済みます。

toyboot4etoyboot4e

Data Structure (1)

データ構造の問題はベンチマークテストを兼ねており、基本装備を強化できます。中盤から木が増えそうです。

Associative Array

436 ms. maspy さんの HashMap (Int -> a のみ) を写経しました。座標圧縮 (O(N \log N)) よりも速いです！　計算量を書けば確かにですが、感動しました。

TODO: 任意のデータ型をキーとしたいです。

Predecessor Problem

2 分木のベンチマークができます。

  • IntMap: 2256 ms
    心もとないスピードです。

  • DenseIntSet: 582 ms
    maspy さんの FastSet こと64 分木、もとい hibitset を写経してみました。引数は Int のみで定義域は [0, n) に限定されます。なぜかそこまで速くありません。 TODO: bitvec に替えてみたいです。

  • Splay 木 (unboxed vector 製): 2086 ms
    IntMap よりも僅かに速いものの、イマイチ。

Double-Ended Priority Queue

  • IntMap ベースの MultiSet: 910 ms
    やはり遅いです。座標圧縮して 64 分木を使ってみる？　maspy さんの Double_End_Queue を見てみたいです。

Unionfind

84 ms. 特に問題無し！

Static Range Sum

209 ms. 累積和の取得演算子 +! をテストできました。

Static RMQ

310 ms. 正格セグメント木 (区間取得 (可換))

Point Add Range Sum

249 ms. 正格セグメント木 (1 点更新、区間取得 (可換)) 。

Point Set Range Composite

454 ms. 正格セグメント木 (1 点更新、区間取得 (非可換)) 。

Range Affine Point Get

911 ms. 遅延セグメント木 (区間更新、 1 点取得 (可換)).

Range Affine Range Sum

273 ms. 遅延セグメント木 (区間更新、区間取得 (可換)). Vertex Set Path Composite の affine 変換とは合成の順序が逆です。どちらかの順序に実装を合わせて、もう一方の問題では Dual モノイドに包むのが良さそうです。

Range Set Range Composite

2,778 ms. 遅延セグメント木 (区間更新、区間取得 (非可換)).

Range Chmin Chmax Add Range Sum

225 ms. Segment Tree Beats!

Range Kth Smallest

356 ms. 最小限の Wavelet Matrix

toyboot4etoyboot4e

Data Structure (2)

Point Set Range Sort Range Composite

Range Reverse Range Sum

856 ms: 反転可能 splay tree. 遅延評価の抽象化に無駄があって 100ms ほど余分に遅いです。

​Dynamic Sequence Range Affine Range Sum

3,376 ms: 遅延伝播反転可能 splay tree.

..

Queue Operate All Composite

187 ms. Stack で SWAG. Deque 版で解くと 219 ms でした。

Deque Operate All Composite

220 ms. Deque で SWAG.

Static Range Frequency

1,350 ms. Wavelet Matrix. IntMap 解法とほぼ同速なのがショックです。

Static Range Count Distinct

1,378 ms. Wavelet Matrix. Verify というか応用的な問題です。元ネタとして D-Query という問題があるようです。

toyboot4etoyboot4e

Graph (1)

グラフ序盤では、重み有りグラフや経路復元を要求する問題が多いです。グラフ抽象化を見直す機会となります。

Cycle Detection (Directed)

391 ms. 閉路検出 (有向グラフ)

Cycle Detection (Undirected)

340 ms. 閉路検出 (無向グラフ)

Shortest Path

268 ms. Dijkstra 木。 Dijkstra の引数は Sum, Max, Min をまとめる何かにした方が良い気がしています。

Strongly Connected Components

398 ms. SCC. 高速化したいです。

toyboot4etoyboot4e

Tree

木ではとにかく HLD が強いようです。 maspy さんのライブラリにおいても単なる Tree が HLD を持ちます。やはり HLD が木を解く主要なデータ型と言えそうです。

Tree Diameter

260 ms. こういうのが一瞬で求まる環境を作っておくのが良いですね。

Lowest Common Ancestor

430 ms. HLD. ダブリングより HLD の方が速かったです。ダブリング (binary lifting) は、ライブラリとしてはアンチパタンかもしれません (mod 上の逆元 → exgcd、 LCA → HLD, suffix array → SA-IS など)

Jump on Tree

552 ms. HLD. Vertex Add Path Sum 等で作った簡素な HLD が魔改造される問題です。まだ強くなるというのか……！

Frequency Table of Tree Distance

未回答

Rooted Tree Isomorphism Classification

未回答

Tree Path Composite Sum

339 ms. 辺に重みがあるタイプの全方位木 DP です。 Op と Acc の関係は既存コードのままに、 onEdge :: op -> (Vertex, w) -> op を追加しました。

Vertex Add Path Sum

646 ms. HLD (頂点に重み、可換).

Vertex Set Path Composite

431 ms. HLD (頂点に重み、非可換). 木において辺の重みを頂点に載せるテクニックがあり、 ABC 294 - G も重要です。 maspy さんの Tree_Monoid を写経して実装しました。

Vertex Add Subtree Sum

404 ms. HLD. Index 後の頂点 (頂点’) について、部分木の頂点' はすべて連続しているため、部分木のサイズを記録しておけば部分木の可換モノイドを一括で畳み込めます。辺を畳み込む場合もほぼ同様でしょう。

..

Dynamic Tree Vertex Add Path Sum

1,118 ms. LCT, 可換モノイド。辺の追加 (link), 削除 (cut) とパスの畳み込みをやります。パスの畳み込みは preferred path の根における集約でした。非可換モノイドに非対応ならば 150 ms 程度速くなります。

Dynamic Tree Vertex Set Path Composite

1,749 ms. LCT, 非可換モノイド。ノードに逆向きの畳み込みも持たせます。

Dynamic Tree Vertex Add Subtree Sum

1,470 ms. LCT, 部分木の畳み込み。これまでは集約を同じ preferred path 内のノードに限定していましたが、 path-parent も集約の対象とします。

toyboot4etoyboot4e

Convolution

大前提が DFT! 連続信号を離散化し、周期関数に拡張した上で高周波成分をカットすると、元の信号を N 個の周波数成分で表現できます。理論が重い。

Convolution

1,285 m4 NTT. 大変過ぎた上に、まだ 10 倍高速化できるようです。

toyboot4etoyboot4e

Linear Algebra

ジャッジ環境に線形代数ライブラリが無いこともあり、逆行列までは欲しいですね。

Matrix Product

5,333 ms. 行列積。意外にバグっていてショックでした。しかも遅い。 HasCallStack を消すと 500 ms ほど速くなりました。

Matrix Product (Mod 2)

Bitset で 64x 高速化？

Pow of Matrix

4,453 ms. 行列累乗。 stimes の正格評価版を作って使います。

Determinant of Matrix

行列式

..

Rank of Matrix

階数

..

Inverse Matrix

逆行列

toyboot4etoyboot4e

String

文字列も苦手です。高度な上に、要求に際限がありません。

Z Algorithm

22 ms. 小気味好い線形アルゴリズムです。使い方……？

Enumerate Palindromes

未回答

Suffix Array

215 ms. ダブリングで何とか。 SA-IS ……

Number of Substrings

203 ms. LCP Array. 応用？

..

Longest Common Substring

Suffix Array?