競プロ Advent Calendar 2022 の 1 日目担当の Nachia です。よろしくお願いします。
時間で変化する状態については、 2022/11/10 以降に取得した情報で書きます。
ライブラリ作り（盆栽）って？
※この section だけキモい語り方をします
競技プログラミングでは、計算量で差がつくアルゴリズムがよく出題されます。有名な方法は特に何度も出題されるので、あらかじめプログラムを用意しておきます。
それの面白さって何？
ライブラリは基本的に高速であるほうがよいです。また、ライブラリ全体で多くの場合をカバーできるほうがよいです。心血を注いで書いたプログラムが公開されているなかで最速実行時間を出してﾆﾁｬると気持ちいいです。
yosupo さんによって Library Checker というサイトが運営されており、ライブラリ作りの楽しさと効率が何倍にもなっています。たすかる
なぜ Library Checker なのか？
- AtCoder の問題でもできるのですが、 AtCoder の提出中の最速は本当に速いので勝てません（おい）。 Library Checker で提出が過疎の問題に高速なプログラムを提供することで気持ちよくなれます。
- Library Checker の問題は基本的に背景に出題例があり、今後コンテスト本番でもライブラリを出してドヤることが期待できます。
- 競プロerが参照しやすい場所であるがゆえ、放っておいても他競プロerに使ってもらえるチャンスがあるので、日本の競プロ界隈に貢献した気になれるかもしれません。
- 難しいアルゴリズムを学ぶ機会になるので、単純に勉強になります。
俺のデッキ
本当はもっとありますが、他競プロerによって山ほど公開されているので、特に形式を整えたもののみ公開しています。
ちなみに Library Checker の AC 数は 113 です。
記事の方針
この記事は修正依頼以外で更新しません。
想定解法を含む既知の解法への言及を省略することがあります。私の提出での解法と最速解法に注目します。
この記事本体ではあまり詳しく書きません。貼ってあるリンクは偶々知っていたものとアドリブで検索して出てきたものです。
用意しておくべきもの
高速入出力
持ってなかったら Nyaan’s Library から借りることをおすすめします。私のものも一応 CC0 ライセンスで公開しています。(11/10時点のリンク、切れてたらすみません)
AtCoder Library
畳み込みが速いので、多項式系のライブラリを作るときは正直 AtCoder Library の NTT を使ったほうがよいです。自作の NTT を実装したら、そのときに移行しましょう。少しでも深淵に触れたい場合は Nyaan’s Library にある AVX2 を利用した実装を見るとよいです。 ’22 高専プロコンでは Nyaan’s Library を主にインターフェースを改造して使用しました。
ACL のアルゴリズムは NTT 以外も高速です。
各問題の解法の解説
Data Structure
Associative Array
99235 赤黒木の insert を実装して試していました。
82081 別に Library Checker で標準ライブラリを使ってはいけないというわけではないです。
Predecessor Problem
99482 64分木を探索します。
64 分木が速いだろうと思っていましたが、 fastest には VEBTree の文字とそれっぽい実装が見えるので、複雑なアルゴリズムである van Emde Boas tree が意外にも効率的らしいです。
Unionfind
54763 コードの見た目がキモいですが、 weighted union rule を省いた償却 $log (n)$ タイプの Union-Find です。正直 C++ で競プロをする範囲では困らないと思います。
（ ACL （や、その言語移植版）があるのでそっちを使おうそうしよう）
Static Range Sum
26206 累積和(prefix sums) を取るとクエリ $O(1)$ で答えられます。ライブラリにしたとして使って楽になるところが果たしてあるのですか？
最近 noshi さんが suffix sums を流行らせようとしていた
Static RMQ
83554 sparse table です。
前計算 $O(N)$ クエリ $O(1)$ のアルゴリズムがあります（ noshi さんの記事）。
Point Add Range Sum
55280 binary indexed tree (BIT) です。
これは segment tree か BIT くらいしかないと思います。
Point Set Range Composite
26215 segment tree (セグ木)です。
区間積だけ取るセグ木はさすがに再帰関数にしないほうがよいです。
Range Affine Range Sum
74392 遅延セグメント木です。
遅延セグ木も区間作用区間和なら再帰関数にしなくてもあまり難しくないです。
Range Chmin Chmax Add Range Sum
39506 Segment Tree Beats! の Task. 2 です。原理は分かっても、集約関数を正しく書くのは難しいです。
Range Kth Smallest
74643 wavelet matrix (解説) の典型クエリです。簡単に説明すると、数列を上位ビットからソートする過程を記録しておいて、その構造の上で二分探索します。区間の端が移動する先を前計算すると高速になります。
平方分割のセグ木（更新 $O(1)$ 、クエリ $O(\sqrt{n})$ ）を使って Mo’s algorithm をすると計算量 $O(n\sqrt{n})$ になり、こちらも十分高速です。
Point Set Range Sort Range Composite
比較的新しい問題。
delete を呼ぶようにしたら遅くなったのが気になっています。たぶん trie の底は $2$ よりも $4$ のほうが効率的です。
Vertex Add Path Sum
81513 heavy-light decomposition (HLD) + BIT です。
heavy-light decomposition で分解した後に処理する列クエリのデータ構造は HLD と無関係にしているので、 BIT でもできます。
完全に余談ですが、Library Checker には無い問題で、データが静的なら累積和や disjoint sparse table を使えるのでより高速になります。深淵には前計算 $O(n\alpha (n))$ クエリあたり $O(\alpha (n))$ のアルゴリズムがあるらしいです。
Vertex Set Path Composite
72675 heavy-light decomposition (HLD) + segment tree です。
HLD に何でも乗るので、正直 Vertex Add Path Sum はいらないと勝手に思っています。
Vertex Add Subtree Sum
88212 heavy-light decomposition (HLD) + segment tree です。
この形の部分木は dfs 順をとると区間 $1$ 個になるのでクエリあたり $O(\log n)$ です。
Vertex Add Range Contour Sum on Tree
100300 重心分解二分探索木（仮称）です。原理はこのブログで解説しました。
比較的新しい問題。
集約は min とか product (mod composite) でもできますが、 verify 用の問題なので sum のほうが適切だという議論が forum にあります。
Dynamic Sequence Range Affine Range Sum
77455 splay tree です。永続化は不要なので大丈夫です。
一応このブログで解説していますが、そのうち別のを書くつもりです。
range reverse があるので、 split が高速な splay tree が高速です。また、左端を min_left 、右端を max_right で指定すると splay tree の split-merge がさらに高速です。 noexcept を付けられる呼び出しが多く、高速化します。
制約でかすぎないか
113172 赤黒木もやりました。
Dynamic Tree Vertex Add Path Sum
76997 splay する link-cut tree です。
作り方はこれの 211 ページ以降を見て、さらに evert（根の変更）を作ればできます。二分木の reverse は上でやったのでできますね。
OI で書いてイキりましょう
Dynamic Tree Vertex Set Path Composite
100260 sum の代わりに composite するだけです。可換でないので reverse が必要になります。
Dynamic Tree Vertex Add Subtree Sum
78723 link-cut tree です。可換で可逆なので、パスをつなぎかえるときに処理を入れることで木全体の和を求めることができます。
木全体の和を求めるのには euler tour tree (解説) や top tree がありますが、 link-cut tree のほうが断然速いです。
Dynamic Tree Subtree Add Subtree Sum
78634 euler tour tree (解説) です。
link-cut tree でも頑張るとできるらしいです。当然 top tree でできます。
Dynamic Graph Vertex Add Component Sum
101322 dynamic connectivity (解説) です。
オフラインで処理できる断然高速な方法もあります。以前テストケースで出てくる連結成分が全部小さかったので、大きいケースを入れたら何十倍も遅かったです。
Set Xor-Min
30003 binary trie を探索します。
Line Add Get Min
42308 Li-Chao tree です。セグ木の作用が合成できないときに、左右どちらか一方のみしか探索する必要がないようにします。
convex hull trick 周りはよく知りませんが、この問題ならほかの解法もあります。
Segment Add Get Min
55451 Li-Chao tree です。
この問題になると Li-Chao tree くらいしかないと思います。
Queue Operate All Composite
30049 逆元を作れることを悪用した変な解法です。
ここでの良い解法は SWAG と呼ばれるものです。（競プロ範囲ではこの解法のデータ構造を SWAG と呼んでそうな場合しか知らない）
Deque Operate All Composite
100853 stack を $2$ 個使って償却 $O(1)$ の deque を作ります。
空になったらもう一方の stack から半分とってきます。
Static Range Frequency
63462 wavelet matrix の典型クエリです。 (解説) （ 2 回目）
Static Range Inversions Query
55306 数列を平方分割していろいろします。何したか忘れました。
主に基数ソートをがんばると $O(N\sqrt{N})$ になります。
noshi91 「こんなところに噂の Mo を使う問題が！解くしかないな」というように、典型的な BIT を持つと Mo’s algorithm ができるので、それ系の verify になります。
Rectangle Sum
76491 wavelet matrix と同様の構造にして、長方形クエリを $O(\log n)$ 個の区間クエリに分解します。区間クエリは累積和で処理できます。
オンラインでないといけないというルールは無いので、平面走査を用いたオフライン処理も verify できます。
Point Add Rectangle Sum
86582 点を全部先に読み込んで Rectangle Sum を更新付きでやります。区間クエリはセグメント木で処理できます。
Persistent Queue
39110 $O(\log n)$ 個のポインタを持って binary lifting する違法解法です。
Persistent Unionfind
39182 集約値を持たない永続セグメント木で永続配列として、それで Union-Find を実装します。
Graph
Cycle Detection (Directed)
75952 dfs の返り値を使うパターンです。ライブラリ化してません。
Shortest Path
65657 ダイクストラ法です。
ダイクストラ法は毎回微妙に違うのを書くので、特にライブラリ化していません。
Strongly Connected Components
106347 再帰しない dfs で Kosaraju のアルゴリズムをします。
fastest 付近には Tarjan のアルゴリズムがよく見られます。
K-Shortest Walk
105772 Eppstein’s algorithm というらしいです。原理はこの解説記事をただ 1 つの頼りにしました。
永続 heap の erase をやると遅いので、 $2$ つの子をそのまま queue に入れるのが重要です。
Two-Edge-Connected Components
106412 再帰しない dfs で lowpt を計算し、各辺が橋かどうか判定します。そのあと、 dfs 順に頂点を見て、橋をまたいだときに新しい成分を作ります。まず頂点に成分番号を振り、そこからリストを作ります。
Matching on Bipartite Graph
105507 $2$ 部グラフに特化した方法で増加路を見つけます。詳しいことは自信がないのでここでは言わないことにします。
dinic 法のライブラリでやると辺のリストや流量の管理が重たいので、マッチングに特化したライブラリを作ります。
Assignment Problem
59020 最小費用流の Primal-Dual で、密グラフ用のダイクストラ法( $O(n^2)$ )を使います。
Directed MST
78064 Chu-Liu/Edmonds’ algorithm を skew heap で実装します。
つまり、 heap のマージを使って Borůvka（ブルーフカ）法の応用で解けます。
詳細を解説できるほど覚えていないし、そもそもこのプログラムがバグっぽい挙動を見せています。
Manhattan MST
各点の周囲で 45 度ずつにわけてそれぞれ最近点を取ると、必要な辺がすべて得られるらしいです。これを逆向きにやっている実装を見つけたので、写経…
正当性があるのかはまだ知りません。
Maximum Independent Set
101591 次数 $1$ 以下の頂点はその場で処理しながら、次数最大の頂点を使うか使わないかを選んで分岐します。次数 $2$ だけになったらその場で解きます。どうやら半分全列挙よりはたいてい速いようです。
Chromatic Number
68207 ある条件で塗る方法を数え上げ、 0 or 1 を判定します。
68427 適当な mod を取って 0 or 1 を推定します。
数え上げの方法は、このブログで解説しています。
Enumerate Triangles
107621 forum に貼ってあるリンクの先のスライドを見ましょう。
次数の大きいほうから小さいほうに辺を向きづけて DAG を作るとできます。
ABC258G – Triangle が通るらしいです。
計算式の特徴を利用した最適化がありますが、それで最適化していない提出のうちではほぼ fastest かな？
Enumerate Cliques
100889 次数の小さい頂点を選ぶと他に選べる頂点が少なくなるのがポイントです。
計算式を累積で計算すると速くなりますが、ライブラリ実装がめんどくさい割に非本質なのでやってません。
Tree Decomposition (Width 2)
111917 PathSearch です。
SPQR-tree の下位互換+非 biconnected みたいな問題です。（ R が無い場合のみ計算して S だけ出力みたいな）
次数 $2$ 以下の頂点を見つけてそれに対応するノードを作って多重辺を除去するのですが、 SPQR-tree の PathSearch と同様に隣接リストを構築して ESTACK を管理すると多重辺がいい感じに全部見つかるものと認識しています。 lowpt2 は不要です。
SPQR-tree に対する私の認識は、このブログである程度共有しています。それをもとに実装した SPQR-tree 構築プログラムもあります。
Chordal Graph Recognition
102683 forum に “O(nlogn) or O(n)” と書いてあるので $O(n)$ で実装しました。
forum が何を言っているのか分からないので、 kazu0x17’s diary を読みました。
induced cycle を $O(n)$ で見つける方法はツイートしたのでそれを見てください。
あと辺の有無の判定を調整して全体 $O(n)$ を達成します。
Tree
Tree Diameter
102970 任意の頂点から始めて、最遠点に移動することを $2$ 回すると直径になります。 double sweep というらしいです。
Lowest Common Ancestor
83641 heavy-light decomposition (HLD) です。パスの深さを揃えてから $1$ つずつ登ります。
83623 オンライン $O(N+Q)$ にする方法もあります。これは RMQ に発展します。
Jump on Tree
97376 heavy-light decomposition (HLD) です。単純にパスを登ります。
level ancestor problem の上位互換のような問題です。
Cartesian Tree
29878 segment tree で RMQ を処理して愚直に構築しました。
$O(N)$ やらないで放置しています。
Frequency Table of Tree Distance
91883 木を重心分解して分解の過程で畳み込みを使用して計算します。重心分解を用いて ${}_N\mathrm{C}_2$ 本のパスを分類して数え上げる問題は過去にこのブログで紹介しました。
Rooted Tree Isomorphism Classification
106413 ボトムアップに計算できます。
小さい部分木について分類されていれば、その multiset の分類になるので、ボトムアップにすると $O(N\log N)$ でシンプルに実装できます。基数ソートを頑張ったり、最後に SA-IS を使ったりすると $O(N)$ になります。
Math
多項式関係の問題は maspy さんがmaspyのHPにまとめてくれています。すごいです。
Counting Primes
77251 $1$ から $\sqrt{N}$ まで普通にやって、残りは $N$ を $k$ で切り捨て除算した値で分類するやつの上でエラトステネスの篩をやります。
えびちゃんさんのブログを読んで実装しました。
Enumerate Primes
77249 普通のエラトステネスの篩です。
高速化のテクニックがいろいろあるらしいです。
Factorize
107617 Pollard’s rho algorithm(ポラード・ロー素因数分解法)です。乱数の品質は気にしていません。
問題設定がポラード・ロー のような高速な素因数分解を要求しています。試し割り系の verify は yukicoder で問題を探すほうがよさそうです。
Stirling Number of the First Kind
109031 talor shift して掛けると二分累乗法のようにできます。
Stirling Number of the Second Kind
$$S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}i^n=\sum_{i=0}^{k}\frac{(-1)^{k-i}}{(k-i)!}\cdot\frac{i^n}{i!}$$
Bernoulli Number
33534 Wikipedia に書いてある式を $\bmod\ 998244353$ で計算します。
$$B_n=n!\cdot\left\lbrack x^n \right\rbrack \left\lparen\frac{x}{e^x-1}\right\rparen$$
Partition Function
55795 maspyのHP より。オイラーの五角数定理です。
$$\sum_{n=0}^{\infty}F(n)x^n=\frac{1}{\sum_{n=-\infty}^{\infty}(-1)^{n\bmod 2}x^{n(3n-1)/2}}$$
Montmort Number
28036 $a_k=(a_{k-1}+a_{k-2})(k-1)$
Sum of Totient Function
111017 乗法的関数の累積和を管理して、 $\zeta(s-1)/\zeta (s)$ を計算します。
これの意味および実装の原理は maspyのHP （多項式とは別のページ）で詳細に説明されているので、これを読みました。
Kth term of Linearly Recurrent Sequence
53356 Bostan-Mori 法です。つまり、
$$\frac{P(X)}{Q(X)}=\frac{P(X)Q(-X)}{Q(X)Q(-X)}$$
とするだけで分母が偶数次だけになるので、偶数次か奇数次のどちらかしか計算しなくてよくなります。これをもとに NTT のセットアップのタイミングを最適化すると NTT の回数が減ります。
Sum of Floor of Linear
100298 $x=i,y=(Ax+B)/M$ のグラフ（関数）を作り、 $M$ の整数倍の部分（自明）を計算したあと、軸を入れ替えると、ユークリッドの互除法になります。
Kth Root (Integer)
102468 境界値を constexpr で埋め込んで、クエリごとに二分探索します。
Discrete Logarithm
100516 Baby-Step, Giant-Step(BSGS) と呼ばれる方法です。
$X$ と $M$ が互いに素な場合に帰着すると逆元が取れるので平方分割のようにして探索します。
Tetration Mod
100619 再帰的に計算すると、実は $B$ が大きいのはあまり意味がありません。
自明なケースを場合分けした後、指数は $\mod{\phi(M)}$ （ $\phi(M)$ はオイラーの totient 関数）と、 $\phi(M)$ 以上かどうかのみわかればよいです。
tatyam さんの記事がよく参考になります。
Nim Product ($\mathbb{F}_{2^{64}}$)
109537 スナネコさんの投稿 に書いてある式を計算します。
ただし、環の性質を使って呼び出しを $5$ から $4$ に減らします。
$$a\otimes b=((a_u\oplus a_l)\otimes(b_u\oplus b_l)\oplus a_l\otimes b_l)\times 2^{2^d})\oplus(a_u\otimes b_u\otimes 2^{2^d-1})\oplus(a_l\otimes b_l)$$
$\#_p$ Subset Sum
59265 こうして
$$\prod_{p=1}^T\left\lparen\frac{1}{1-X^p}\right\rparen^{A_p}=\exp\left\lparen -\sum_{p=1}^TA_p\log\left\lparen1-X^p\right\rparen\right\rparen$$
$\log$ を頑張って計算します。
2 Sat
106514 リテラルに対応する頂点を作り、因果関係を辺で表したとき、同じ強連結成分内で矛盾すると充足不可です。蟻本に載っています。
Convolution
Convolution
88435 NTT です。
NTT(数論変換)は $2\times 2$ の行列の計算をたくさんすればできて、逆変換は NTT 後に先頭以外 reverse 、 $\frac{1}{\text{len}}$ 倍すればできます。 NTT → 各点積 → inverse NTT で巡回畳み込みになります。
Convolution (Mod 1,000,000,007)
78173 良い除数 $3$ つで計算して Garner のアルゴリズムで復元します。
Garner のアルゴリズムの計算は $\bmod 1\ 000\ 000\ 007$ でできるので、 $64$ ビット整数型で足ります。
Convolution (Mod 2^64)
78191 良い除数 $5$ つで計算して Garner のアルゴリズムで復元します。
$\mod{2^{64}}$ の加減乗算は unsigned long long 型の演算で呼べます。
Convolution (Large)
110478 長さ $2^{23}$ に収まる範囲で NTT で計算し、残りは筆算します。
Subset Convolution
77583 $a_n \leftarrow\lambda^{\text{popcount(n)}}a_n$ のようにして bitwise OR convolution したあと、 $c_n \leftarrow \left[\lambda^{\text{popcount(n)}}\right]c_n$ のようにします。（伝われ）
Bitwise And Convolution
33070 多次元累積和（ゼータ変換）→各点積→逆変換です。
Bitwise Xor Convolution
103120 アダマール変換というセットアップをします。多次元 FFT とも解釈できます。
Multivariate Convolution
70820 $a_n \leftarrow\lambda^{(\sum d)\bmod K}a_n$ のようにして convolution （ $\lambda$ については巡回 ）したあと、 $c_n \leftarrow \left[\lambda^{(\sum d)\bmod K}\right]c_n$ のようにします。（伝われ（無理））
Convolution on the Multiplicative Monoid of $\mathbb{Z}/2^N\mathbb{Z}$
100750 添え字を $\pm 5^k$ で表すといい感じになります。
Polynomial
(Inv,Exp,Log,Pow) of Formal Power Series
Inv : 100745
Exp : 82103
Log : 69704
Pow : 109026
opt さんの記事を読んで実装したのですが、今見たら見つかりませんでした。たぶん消えてます。
Composition of Formal Power Series
$\lceil\sqrt{N}\rceil$ 乗までと $t\lceil\sqrt{N}\rceil$ 乗を計算し、それぞれ長さ $2N$ で NTT セットアップすると行列積っぽい形になります。計算量は $O(N^2)$ です。
(Inv,Exp,Log) of Formal Power Series (Sparse)
Inv : 96668
Exp : 94364
Log : 94046
forum にやり方が書いてあります。
Multipoint Evaluation
109212 $f(x)\bmod (x-p_i)$ を計算したいので、 $f(x)\bmod \prod_{i=l}^{r-1}(x-p_i)$ をセグ木に載せる感じでトップダウンに計算します。参考：37zigenのHP
Polynomial Taylor Shift
109028 畳み込み $1$ 回です。
$$b_i=\sum_{k=i}^{N-1}\binom{k}{i}a_kc^{k-i}=\frac{1}{i!}\cdot\sum_{k=i}^{N-1}(k!a_k)\cdot\frac{c^{k-i}}{(k-i)!}$$
Division of Polynomials
109210 定数項を非 $0$ にしてから、 reverse して Inv of FPS を計算します。
Matrix
Matrix Product
73280 愚直に計算します。
高速化したい場合は Strassen 法 が強いらしいです。
Determinant of Matrix
73148 シンプルな掃き出し法です。学校で習うと思います。
System of Linear Equations
76195 rank が増えないときの場合分けを除けばシンプルな掃き出し法です。学校で習うと思います。
Inverse Matrix
55701 掃き出し法と同時に単位行列を変形します。学校で習うと思います。
Characteristic Polynomial
105016 普段よりも $1$ 行下を使って掃き出した後、ほかの列から $\lambda$ を借りてきて余分な $\lambda$ を消去します。階段+$\alpha$ みたいな行列ができるので、 DP します。
String
Z Algorithm
56227 Z algorithm です。
snuke さんのブログを見て実装しました。
Enumerate Palindromes
58968 Manacher のアルゴリズムです。
snuke さんのブログを見て実装しました。
Suffix Array
79128 ペアのソートを $O(\log(n))$ 回繰り返します。蟻本に載っています。
Number of Substrings
79132 Longest Common Prefix Array(LCP array) の総和から計算できます。
LCP array は蟻本に載っています。
Run Enumerate
96977 Main-Lorentz Algorithm (?)です。 pazzle1230さんの解説ブログ があります。
個別問題の解説スライドも読みました。
Geometry
Sort Points by Argument
69426 座標の符号で $3\times 3$ 区画に分け、それぞれで比較関数に外積を使ってソートしました。
New
Area of Union of Rectangles
109971 ( $\min$ , $\min$ の個数 ) を管理する遅延セグ木で走査します。
Range Affine Point Get
100755 Affine だけ乗せる遅延セグ木です。これ専用問題っぽい。
Product of Polynomial Sequence
111988 $2$ べきにパッキングするヒューリスティックを入れました。 $\log(n/x)$ 型(?) の要件を満たしつつ線形時間です。
Gcd Convolution
77250 ゼータ変換をセットアップにします。
Lcm Convolution
77305 Gcd Convolution と逆方向に累積和をとります。
Primitive Root
109014 $g$ を乱択して、 $p-1$ の素因数 $q$ について $g^{\frac{p-1}{q}}\bmod p\neq 1$ を確認します。
ポラード・ロー級の高速素因数分解が要求されています。
Longest Increasing Subsequence
97680 Increasing Subsequence の $k$ 番目の要素になれるような最大の $k$ を各要素について求めます。逆からも求めます。
Number of Subsequences
97649 最後の文字を状態にした dp テーブルと、その総和を管理します。
Biconnected Components
106441 DFS で lowpt を計算し、もう一度探索して成分に分けます。
Static Rectangle Add Rectangle Sum
100406 線形関数を管理する Binary Indexed Tree (BIT) で走査します。
さいごに
つよい アルゴリズム よわい アルゴリズム そんなの ひとの かって ほんとうに つよい 競erなら すきな アルゴリズムで かてるように がんばるべき
adhoc 「は？」
