2020-02-19

競プロのアルゴリズム関連略称まとめ

随時募集しています

略称	正称
APSP	All Pairs Shortest Path
BB	Branch and bound
BBST	Balanced Binary Search Tree
BFS	Breadth First Search
BIT	Binary Indexed Tree
BM	Berlekamp-Massey
BM	Boyer-Moore
BSGS	Baby-Step Giant-Step
CHT	Convex Hull Trick
CRT	Chinese Remainder Theorem
D&C	Divide and Conquer
DAG	Directed Acyclic Graph
DEPQ	Double-ended priority queue
DFS	Depth First Search
DP	Dynamic Programming
DST	Disjoint Sparse Table
DSU	Disjoint Set Union
ET	Euler Tour
ETT	Euler Tour Tree
FFT	Fast Fourier Transform
FMT	Fast Modulo Transform
FPS	Formal Power Series
HLD	Heavy Light Decomposition
IP	Integer Programming
KMP	Knuth-Morris-Pratt
LA	Level Ancestor
LCA	Lowest Common Ancestor
LCP	Longest Common Prefix
LCS	Longest Common Subsequence
LCT	Link Cut Tree
LCT	Li Chao Tree
LIS	Longest Increasing Subsequence
LLRBT	Left-Leaning Red-Black Tree
LP	Linear Programming
MC	Max Clique Problem
MCF	Minimum Cost Flow
MIS	Maximal independent set
MST	Minimum Spanning Tree
NTT	Number Theoretic Transform
PQ	Priority Queue
RBST	Randomized Binary Search Tree
RBT	Red-Black Tree
RLE	Run Length Encoding
RMQ	Range Minimum Query
RSQ	Range Sum Query
RUQ	Range Update Query
SA	Suffix Array
SAT	satisfiability problem
SCC	Strongly Connected Components
SPFA	Shortest Path Faster Algorithm
SSP	Shortest Superstring Problem
SSP	Successive Shortest Path
SSSP	Single Source Shortest Path
SWAG	Sliding Window Aggregation
TSP	Travelling salesman problem
UF	Union Find
WF	Warshall Floyd
WM	Wavelet Matrix

2020-01-15

みんぷろ2018決勝-A Uncommon Θ(Alog(log(A)))

アルゴリズム

A - Uncommon

これを $A := \max(a_i,m)$ として時間計算量 $\Theta(A \log(\log(A) ) )$ で解きます。

$\gcd$ 畳み込み

ゼータ変換・メビウス変換を理解する - Qiita
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ
添え字の $\gcd$ での畳み込みをおおまかに理解しているとします。 $g(x) := \sum_{x|d} f(d)$ は行列 $M$ を用いて $g = Mf$ と表現できます。これを軸にして式変形を行います。

値の定義と記法

添え字は 1-indexed
アイバーソンの記法 - Wikipedia

行列 $M$
$M_{i,j} := \lbrack i | j \rbrack$
単位ベクトル $e_i$
$(e_i)_j := \lbrack i = j \rbrack$
入力 $a$ を表すベクトル $v$
$v_i := \# \lbrace j \mid a_j = i \rbrace$
ベクトル同士の各点積 $\circ$
$(x \circ y)_i := x_i y_i$
演算子の優先度は行列積より低いとする

例えば、 $\gcd$ 畳み込みは $M ^{-1}(Mx \circ My)$ となる。
また、 $1 × N$ 行列と $N$ 次元ベクトルの同一視などを断りなく行う。

アルゴリズム

$i$ についての答えは以下のように書くことが出来る。
$(M^{-1}(Mv \circ Me_i) )_1$
$\because$ $v$ と $e_i$ を $\gcd$ で畳み込みすれば、その第 $1$ 成分は $\gcd(i, a_j) = 1$ なる $j$ の個数となる。
これを式変形すると
$= e_1^T(M^{-1}(Mv \circ Me_i) )$
$= (e_1^T M^{-1})(Mv \circ Me_i)$
$= ( (M^T)^{-1}e_1)^T (Mv \circ Me_i)$
$= ( (M^T)^{-1}e_1 \circ Mv)^T(Me_i) \quad \because \ x^T(y \circ z) = (x \circ y)^T z$
$= ( ( (M^T)^{-1}e_1 \circ Mv)^T M)e_i$
よって $i$ に依存しない部分を新しく文字で置いて
$u := ( (M^T)^{-1}e_1 \circ Mv)^T M$
とすれば、求める値は
$ue_i = u_i$
となることが分かった。
すなわち $u$ の各成分を出力すればよい。

$M$ 及びその転置や逆行列とベクトルとの積を $\Theta(N \log (\log (N) ) )$ で計算するアルゴリズムを用いれば、この問題を解くことが出来る。

実装例

Submission #9522125 - 「みんなのプロコン 2018」決勝
分かりやすさのため $\Theta(A \log(A) )$ の実装になっています。
$Mv : {\rm multiple\_zeta}(v)$
$vM : {\rm divisor\_zeta}(v)$
$(M^T)^{-1}v : {\rm divisor\_mobius}(v)$

2019-12-21

列の連結/全要素列挙をする永続データ構造

データ構造

某に載せるほどか...? 載せることにしたらこっちは消えます
以下の操作を実現する永続データ構造が存在する

$make ( x )$
単一の要素 $x$ からなる列を作成する
時間/空間計算量 $\Theta ( 1 )$
$merge ( x , y )$
列 $x , y$ を連結した列を作成する
時間/空間計算量 $\Theta ( 1 )$
$enumerate ( x )$
列 $x$ の全要素を順に列挙する
時間計算量 $\Theta ( | x | )$

アルゴリズム

各要素を葉に持つ二分木 (非平衡) を永続化すればよい。
$merge( x , y )$ は $x$ を左子、 $y$ を右子に持つノードを作る。
$enumerate$ は DFS で木を走査する。

f:id:noshi91:20191221000832j:plain

2019-12-20

単純な最小カットで表現できる条件

アルゴリズム

変数 $x , y$ への $0 , 1$ の割り当てに対してコストが以下の図のようになるとします。

f:id:noshi91:20191220161354j:plain

コストを最小化するとき、 $A + D \le B + C$ ならば最小カットで表現できます。

説明

最小カットで使えるプリミティブな操作を考えます

f:id:noshi91:20191220222121j:plain

また、解に直接値を加えることで全体に $+c,-c$ することが出来ます。
量 $A+D-B-C$ を考えると、 $x \rightarrow y , y \rightarrow x$ の辺で減少し、それ以外では変化しません。よってこれらの辺で表現できる必要条件 $A + D \le B + C$ が得られます。一方これが実際に構築可能であることもすぐに示せます。

変数の反転

一方の変数を反転することを考えると不等号が逆のものが表現できます。よってそのままでは表現できなくても、変数をいくらか反転すると表現可能となる可能性があります。

$A + D \lt B + C$
$x , y$ の反転は一致する必要があります
$A + D = B + C$
反転の有無に関係なく表現可能です
$A + D \gt B + C$
$x , y$ の反転が異なる必要があります

yukicoder 957 植林

行と列が変数です。その列/行一帯を植林することを $1$ とします。すると 2 変数が関わり合う部分のコストは以下のようになります。

f:id:noshi91:20191220184226j:plain

行か列のいずれかを植えることにしたらそのマスは費用を払う必要がある、という意味です。これは $A + D \le B + C$ を満たすことが $G_{i,j} \geq 0$ から分かり、表現可能です。

2019-12-11

(計算量 k 倍) 上位 k 個を取得する Li Chao Tree

データ構造

概要

Li Chao Tree で小さいほうから $k$ 個取得できる
ただし取り出した $k$ 個の順番は保証されない
空間計算量 $\Theta ( k n )$
時間計算量 $\Theta ( k \log ( n ) )$ per query

アルゴリズム

全てのノードは高々 $2 k - 1$ 個の直線を保持します。元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエリが処理できる状態を維持します。

追加

ノードに直線を追加することを考えます。元々入っていた直線が $2 k - 1$ 本未満なら、ただ追加して終わります。そうでない場合、新しい直線と合わせて $2 k$ 本の直線があります。これらのうち、ノードの中央の点での値が最も大きいものを $l$ とします。
$l$ と他の直線を比較すると、 $l$ は左と右の少なくとも一方の区間では完全に大きいです。 $l$ 以外に $2 k - 1$ 個の直線があるため、左と右のどちらかでは $k$ 個以上の直線に対して $l$ は大きくなります。よってそちら側の区間で $l$ は上位 $k$ 個になり得ず、反対側の区間へ再帰的に $l$ を追加すればよいです。

f:id:noshi91:20191211210528j:plain

取得

クエリの点を覆う全てのノードの直線を列挙した後、選択アルゴリズムで上位 $k$ 個を取り出します。

2019-12-07

木の平方分割、出来るもの出来ないもの

アルゴリズム

出来ない分割の例

木に対して、頂点集合をに分割する
- $V _ i$ がつながっている: $V _ i$ 内の任意の頂点対のパスは $V _ i$ に含まれる
- $| V _ i |$ が小さい: $| V _ i | \in O ( \sqrt N )$
- $k$ が小さい: $k \in O ( \sqrt N )$
- 反例: スターグラフ

出来る分割の例

根付き木に対して、頂点集合を $V _ 0, V _ 1, \ldots V _ {k - 1}$ に分割する
- $V _ i$ がつながっている: $V _ i$ 内の任意の頂点対のパスは $V _ i$ に含まれる
- $| V _ i |$ が小さい: $| V _ i | \in O ( \sqrt N )$
- 深さが小さい: 任意の頂点について根からのパスは $O ( \sqrt N )$ 個の $V _ i$ によって被覆される
木に対して、辺集合を $E _ 0, E _ 1, \ldots E _ {k - 1}$ に分割する
- $E _ i$ がつながっている: $E _ i$ の端点として現れる任意の頂点対のパスは $E _ i$ に含まれる
- $| E _ i |$ が小さい: $| E _ i | \in O ( \sqrt N )$
- $k$ が小さい: $k \in O ( \sqrt N )$
次数の最大値が $d$ の木に対して、頂点集合を $V _ 0, V _ 1, \ldots V _ {k - 1}$ に分割する
- $V _ i$ がつながっている: $V _ i$ 内の任意の頂点対のパスは $V _ i$ に含まれる
- $| V _ i |$ が小さい: $| V _ i | \in O ( \sqrt {d N} )$
- $k$ が小さい: $k \in O ( \sqrt {d N} )$
- $d$ が小さい木の例: 二分木 ( $d \leq 3$ )