noshi91のメモ

データ構造のある風景

Lagrange 反転変種チートシート

関連記事

Lagrange inversion theorem - Codeforces

[Tutorial] Generating Functions in Competitive Programming (Part 2) - Codeforces

公式集

注意: 一応証明したつもりですが、係数環を一般の可換環に取るところが怪しいです

逆関数の係数

\begin{alignat}{2} \lbrack x ^ n \rbrack G(x) & {} = \frac{1}{n} & \lbrack x ^ {- 1} \rbrack & F(x) ^ {- n} \cr & = {} & \lbrack x ^ {- 2} \rbrack & F(x) ^ {- n - 1} F'(x) \cr & = \frac{1}{n} & \lbrack x ^ {n - 1} \rbrack & \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n - 1} \rbrack & \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

逆関数の冪乗の係数

\begin{alignat}{2} \lbrack x ^ n \rbrack G(x) ^ k & {} = \frac{k}{n} & \lbrack x ^ {- k} \rbrack & F(x) ^ {- n} \cr & = {} & \lbrack x ^ {- k - 1} \rbrack & F(x) ^ {- n - 1} F'(x) \cr & = \frac{k}{n} & \lbrack x ^ {n - k} \rbrack & \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n - k} \rbrack & \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

逆関数との合成

\begin{alignat}{2} \lbrack x ^ n \rbrack H(G(x) ) & {} = \frac{1}{n} & \lbrack x ^ {-1} \rbrack & H'(x) F(x) ^ {- n} \cr & = {} & \lbrack x ^ {-1} \rbrack & H(x) F(x) ^ {- n - 1} F'(x) \cr & = \frac{1}{n} & \lbrack x ^ {n - 1} \rbrack & H'(x) \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n} \rbrack & H(x) \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

さらに一般化したもの

W(x) \in \mathbb A ( ( x ) ) について

\begin{alignat}{2} \lbrack x ^ {- 1} \rbrack W(x) H(G(x) ) = \lbrack x ^ {-1} \rbrack & W(F(x) ) H(x) F'(x) \end{alignat}

証明

補題

\begin{align} \lbrack x ^ {- 1} \rbrack F(x) ^ n F'(x) = \begin{cases} 1 \quad & (n = - 1) \cr 0 \quad & (n \neq - 1) \end{cases} \end{align}

n 倍を含む形式

\begin{align} G(F(x) ) &= x \cr H(G(F(x))) &= H(x) \cr (H \circ G)'(F(x)) F'(x) &= H'(x) \cr (H \circ G)'(F(x)) F(x) ^ {- n} F'(x) &= H'(x) F(x) ^ {- n} \cr \lbrack x ^ {-1} \rbrack (H \circ G)'(F(x)) F(x) ^ {- n} F'(x) &= \lbrack x ^ {-1} \rbrack H'(x) F(x) ^ {- n} \cr n \lbrack x ^ n \rbrack H(G(x) ) &= \lbrack x ^ {-1} \rbrack H'(x) F(x) ^ {- n} \cr \end{align}

n 倍を含まない形式

\begin{align} G(F(x) ) &= x \cr H(G(F(x))) &= H(x) \cr H(G(F(x) ) ) F(x) ^ {- n - 1} F'(x) &= H(x) F(x) ^ {- n - 1} F'(x) \cr \lbrack x ^ {-1} \rbrack H(G(F(x) ) ) F(x) ^ {- n - 1} F'(x) &= \lbrack x ^ {-1} \rbrack H(x) F(x) ^ {- n - 1} F'(x) \cr \lbrack x ^ n \rbrack H(G(x) ) &= \lbrack x ^ {-1} \rbrack H(x) F(x) ^ {- n - 1} F'(x) \cr \end{align}

The 3rd Universal Cup Stage 15: Chengdu - F

単調増加な正実数列 x によって定義される関数 \displaystyle f ( l , r ) := \sqrt{ (r - l) \sum _ {i = l} ^ {r - 1} x _ i } は Monge であることを示せ。

てんぷらによる証明

https://x.com/tempuracpp/status/1854498278190285099

区間の平均値 \displaystyle \mathrm{Av g}(l, r) := \frac{\sum _ {i = l} ^ {r - 1} x _ i}{r - l} を定義すると、 f(l, r) = (r - l) \sqrt{\mathrm{Av g}(l, r)} である。

\begin{align} & & f(l _ 0, r _ 0) + f(l _ 1 + r _ 1) & \leq f(l _ 0 , r _ 1) + f(l _ 1, r _ 0) \cr \iff & & (r _ 0 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 0)} + (r _ 1 - l _ 1) \sqrt{\mathrm{Av g}(l _ 1 , r _ 1)} & \leq (r _ 1 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 1)} + (r _ 0 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 0)} \cr \iff & & \frac{ (r _ 0 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 0)} + (r _ 1 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 1)} }{r _ 0 + r _ 1 - l _ 0 - l _ 1} & \leq \frac{ (r _ 1 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 1)} + (r _ 0 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 0)} }{r _ 0 + r _ 1 - l _ 0 - l _ 1} \end{align}

両辺とも \sqrt{} の凸結合の形であり、引数の凸結合を取ると一致する。 x の単調性から左辺のほうが偏った凸結合になっており、 \sqrt{} が凹関数であることから偏った凸結合ほど小さくなるため求める不等式を得る。 \blacksquare

証明(旧)

問題設定を連続版にする。 すなわち、 x \colon \mathbb{R} \to \mathbb{R} _ {\gt 0} を単調増加な関数として、 \displaystyle f ( l , r ) := \sqrt{ (r - l) \int _ l ^ r x(t) \mathrm d t } の Monge 性を示す。 ここから元の問題の結果も導かれることは明らか。

\displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} \leq 0 が示せれば、 \lbrack l _ 0 , l _ 1 \rbrack \times \lbrack r _ 0 , r _ 1 \rbrack において積分することで f(l _ 0 , r _ 0) - f(l _ 0 , r _ 1) - f(l _ 1 , r _ 0) + f(l _ 1 , r _ 1) \leq 0 が示され、求める不等式を得る。

まず r について偏微分すると \displaystyle \frac {\partial f(l, r)} {\partial r} = \frac{1}{2} \left( \sqrt{\frac{\int _ l ^ r x(t) \mathrm d t }{r - l} } + \sqrt{\frac{r - l}{\int _ l ^ r x(t) \mathrm d t } } x _ {r} \right) が分かる。 \displaystyle A(l, r) := \frac{\int _ l ^ r x(t) \mathrm d t }{r - l} と定義し、これを利用して l について偏微分すると \displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} = \frac{1}{4} \frac{\partial A(l, r)}{\partial l} \left( \frac{1}{\sqrt{A(l,r)} } - \frac{1}{A(l, r) \sqrt{A(l, r)} } x _ r \right) となる。 A は区間の平均値を意味しているから、 x の単調性と合わせると以下の事実が言える。

  • A(l, r) \leq x _ r
  • \displaystyle \frac{\partial A(l, r)}{\partial l} \geq 0

1 つ目の事実から、 \displaystyle \frac{1}{\sqrt{A(l,r)} } - \frac{1}{A(l, r) \sqrt{A(l, r)} } x _ r \leq 0 が分かる。 これと 2 つ目の事実を合わせると、 \displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} \leq 0 が従う。 \blacksquare

1998年東大後期数学第3問

グラフ理論ではないしグラフですらない。列。

解法

両端にダミーの頂点を追加すると、操作 1 は操作 2 で表現できる。 よって操作 2 だけを考えればよい。 最初の頂点も操作 2 で作ることにすれば、問題は以下のように言い換えられる。

頂点 2 つが辺で結ばれている。 操作 2 を好きな回数繰り返して両端以外の全ての頂点を白くするとき、パスの長さ (辺の本数) として取り得る値は何か。

\mathord{\bmod} 3 で 1 と 2 の長さ全てが作れることは簡単に分かる (辺の本数で長さを定義したので 1 ずれているが本質ではない)。 必要性を示す。

定理

2 つの頂点が辺で結ばれており、何らかの色が付いている。 操作 2 を好きな回数繰り返して両端以外の全ての頂点が白くなったとき、以下のいずれかに該当する。

( \mathrm {i} ) 長さが 1 \pmod 3 で、両端はいずれも偶数回色が変化した

( \mathrm {ii} ) 長さが 2 \pmod 3 で、両端はいずれも奇数回色が変化した

証明

パスの長さについての帰納法を用いる。 パスの長さが 1 の場合は自明である。

パスの長さが 2 以上の場合、少なくとも 1 回は操作をしている。 最初の操作によって追加された頂点を c とする。 以降の操作は c より左に行われるものと c より右に行われるものに分けられる。 最終的に両端以外が白になっていることから、 c の左右でそれぞれ帰納法の仮定が適用できる。

最終状態において c より左の部分 ( c を含む) を L、 c より右の部分 ( c を含む) を R とする。 L, R のそれぞれに帰納法の仮定を適用すると、 c が白になっていることから、両者とも ( \mathrm i ) に該当するか、両者とも ( \mathrm {ii} ) に該当するかのいずれかである。

  • 両者 ( \mathrm i ) の場合、全体の長さは 2 \pmod 3 であり、両端は最初の操作で 1 回変化したことを踏まえると奇数回色が変化している。これは ( \mathrm {ii} ) に該当する。
  • 両者 ( \mathrm {ii} ) の場合、全体の長さは 1 \pmod 3 であり、両端は最初の操作で 1 回変化したことを踏まえると偶数回色が変化している。これは ( \mathrm {i} ) に該当する。

よっていずれも定理の主張に該当する。 \blacksquare

余談

操作を最初の 1 回とそれ以降とに分けるのはポリアの壺にも有効な考え方である。 尤も、ポリアの壺には一旦全ての球を区別するという簡潔な解法が存在するが。

1 辺を除いたときの最短路長

問題設定

無向グラフ G = (V, E), 非負の辺重み w \colon E \to \mathbb R _ {\geq 0}, 始点 s \in V, 終点 t \in V が与えられる。 各 e \in E について、 (V, E \setminus \lbrace e \rbrace) 上での s \text{-} t 最短路長を求めよ。

この問題を \mathrm O ( \lvert E \rvert \log \lvert E \rvert) の時間計算量で解くアルゴリズムを説明する。

本質的に同じ問題が https://codeforces.com/contest/1163/problem/F で出題されており、解説するアルゴリズムは tutorial にあるものと同じである。 ただしこの tutorial には証明がないため注意。

アルゴリズム

議論を簡易にするため、まず辺重みは 0 を含まないものとする。 このとき、以下のアルゴリズムが正しく答えを計算する。

まず、 s を始点とする最短路木 T _ s と t を始点とする最短路木 T _ t をとる。 ただし、両者で s \text{-} t パス部分が一致するようにし、それを P とおく。 e \notin P を取り除いたときの最短路長は明らかに w(P) である。

各辺 uv \notin P に対し以下の処理を行う。

  • T _ s における u と t の LCA、すなわち T _ s における s \text{-} u パスが P と分岐する頂点を x とする。
  • 同様に、 T _ t における v と s の LCA を y とする。
  • P 上で x \lt y ならば、 T _ s に沿って s \to u と移動し、 uv を通り、 T _ t に沿って v \to t に至るパスは x と y の間にある各辺 e \in P を通らない。よってそれらの辺に対し、 e を取り除いた際の最短路長の候補に d(s, u) + w(uv) + d(v, t) を追加する。

ただし、 uv は順序対として扱う、すなわち vu にも上記の処理を行うものとする。 処理が全て終わったとき、候補の中で最短のものが求める答えである。 候補の中での最短の計算は、双対セグメント木を使ったり、std::set などのデータ構造を使って imos 法のような処理を行えばよい。

証明

辺 e \in P を固定し、 e に関する答えが正しく計算されることを示す。

補題

任意の頂点 c \in V に対し、以下の両方が成り立つことはない。

  • T _ s における s \text{-} c パスが e を含む
  • T _ t における t \text{-} c パスが e を含む

証明(補題)

同時に成り立つ c \in V が存在すると仮定する。 s \text{-} c パスと t \text{-} c パスが e で交差しているが、 e の前後でパスを組み替えると、合計長が真に短いパスの組が得られるため、それぞれが最短路だったことと矛盾する。 w(e) \gt 0 を使用したことに注意せよ。 \blacksquare

T _ s における s \text{-} c パスが e を 含まない ような c を s \text{-side} 、 T _ t における t \text{-} c パスが e を 含まない ようなものを t \text{-side} と呼ぶことにする。 補題より、全ての頂点は s \text{-side} であるか t \text{-side} である。 両方に該当する頂点は好きな方に割り当てておく。

(V, E \setminus \lbrace e \rbrace) における s \text{-} t 最短路を 1 つとり Q とする。 s は s \text{-side} であり t は t \text{-side} であることから、 Q 上の辺 uv であって u が s \text{-side}, v が t \text{-side} であるものが存在する。 また、 \text{side} の関係から uv \notin P である。 するとアルゴリズム中でこの uv に対して構成されるパスは e を通らず、かつ Q と同じ長さであるため、 e に対する答えが正しく計算される。 \blacksquare

辺の長さが 0 を含む場合

この場合、 T _ s と T _ t の取り方によってはアルゴリズムが誤った答えを返すことがある。 補題が成り立つように適切に取ればよいが、最も証明が明らかな方法は重み 0 の辺を重み \varepsilon にすることである。

注意

有向グラフに対してはこのアルゴリズムは正しく動作しない。 証明において破綻するのは、補題で s \text{-} c パスと c \text{-} t パスの組み換えを行った部分である。

2 要素の分離を網羅するテクニック

概要

n 要素の集合を 2 つに分割することを \log _ 2 n 回行って、どの 2 要素もどこかで分離されているようにすることができる。 向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。

向きの無い分割

問題例

無向グラフ ( V, E ) があり、各辺には正の重みが付いているとする。 U \subseteq V が与えられるので、 u, v \in U, \, u \neq v の条件下で u , v 間の距離の最小値を求めよ。

解法

この問題は Dijkstra 法に少し手を加えると \mathrm O ( M \log M ) で解くことができるが、ここではその解法は思い浮かばなかったことにする。

U を始点とする Dijkstra 法を行うと、どの v \in U に対しても v への距離は 0 となってしまうため上手く行かない。 そこで S \subseteq U を取り、 S を始点とし U \setminus S を終点とする距離を求める。 もし最適な u, v が \lbrace S , U \setminus S \rbrace によって分離されているなら、すなわち \lvert \lbrace u , v \rbrace \cap S \rvert = 1 を満たすなら、これで最適値が得られる。 S を一様ランダムにとれば 1 / 2 の確率でこれは達成されるが、決定性アルゴリズムを得たい。 定式化すると以下のようになる。

問題

集合 U に対し、以下の条件を満たす集合族 \mathcal S \subseteq 2 ^ U を構成する。

  • 任意の x , y \in U, \, x \neq y に対し、ある S \in \mathcal S が存在して、 \lvert \lbrace x , y \rbrace \cap S \rvert = 1

\lvert \mathcal S \rvert は \lvert U \rvert に対しどこまで小さくできるか？

構成と最適性

各 x \in U に対し、 T _ x := \lbrace S \in \mathcal S \mid x \in S \rbrace と定義する。 すると問題の条件は、任意の x , y \in U, \, x \neq y に対して T _ x \neq T _ y と言い換えることができる。 \lvert U \rvert \gt 2 ^ {\lvert \mathcal S \rvert} なら鳩の巣原理によりこの条件は満たされることはなく、逆に \lvert U \rvert \leq 2 ^ {\lvert \mathcal S \rvert} ならば各 T _ x が \mathcal S の相異なる部分集合になるように \mathcal S を定めることができる。 よって \lvert \mathcal S \rvert = \lceil \log _ 2 \lvert U \rvert \rceil が最適である。

元の問題例は \mathrm O (M \log M \log \vert U \rvert) で解けることになる。

向きの付いた分割

この節は ICPC 2023 World Finals Luxor に出題された問題の解法を基に執筆しています。

問題例

有向グラフ ( V, E ) があり、各辺には正の重みが付いているとする。 U \subseteq V が与えられるので、 u, v \in U, \, u \neq v の条件下で u \to v の距離の最小値を求めよ。

解法

有向グラフになったため、最適な u, v に対し u \in S, \, v \notin S を満たす必要がある。 定式化すると以下のようになる。

問題 (ICPC 2023 WF 改題)

集合 U に対し、以下の条件を満たす集合族 \mathcal S \subseteq 2 ^ U を構成する。

  • 任意の x , y \in U, \, x \neq y に対し、ある S \in \mathcal S が存在して、 x \in S, \, y \notin S

\lvert \mathcal S \rvert は n := \lvert U \rvert に対しどこまで小さくできるか？

構成と最適性

前節と同様に、各 x \in U に対し T _ x := \lbrace S \in \mathcal S \mid x \in S \rbrace と定義する。 すると問題の条件は、任意の x , y \in U, \, x \neq y に対して T _ x \nsubseteq T _ y と言い換えることができる。 \lvert \mathcal S \rvert を固定した際にこのような T _ x が最大でいくつ取れるかという問題の解答は Sperner の定理として知られており、 T _ x として大きさ \lfloor \lvert \mathcal S \rvert / 2 \rfloor の \mathcal S の部分集合を選べばよい。 したがって、 \binom d { \lfloor d / 2 \rfloor } \geq \lvert U \rvert となる最小の d が \lvert \mathcal S \rvert の最小値である。 d \in \log _ 2 \lvert U \rvert + \mathrm O ( \log \log \lvert U \rvert ) であり、例えば \lvert \mathcal S \rvert = 21 で \lvert U \rvert = 3.5 \times 10 ^ 5 程度まで構成できる。

ワイルドカードマッチングの高速化

問題

文字集合を \Sigma := \lbrace 0, 1, \dots, \sigma \rbrace とする文字列 S と T がある。 S の長さ \lvert T \rvert の連続部分列のそれぞれについて、 T にマッチするか判定せよ。 ただし文字列がマッチするとは、それぞれの文字列中の 0 を好きな文字に置き換えたときに両文字列が一致することを指す。

解法 (Clifford & Clifford, 2007 [1])

文字列 X と Y がマッチすることと \sum _ i X _ i Y _ i (X _ i - Y _ i) ^ 2 = 0 が同値である。 したがって、各 k について \sum _ i S _ {k + i} T _ i (S _ {k + i} - T _ i) ^ 2 を計算できればよい。 これは括弧を展開して積和形にし、それぞれの項については適切な列を FFT を用いて畳み込めばよい。 時間計算量は O ( \lvert S \rvert \log \lvert S \rvert)。

値域の削減 (Clifford, Efremenko, Porat, & Rothschild, 2009 [2])

前述した解法は最終的に 0 か判定したい値が \lvert S \rvert \sigma ^ 4 程度まで大きくなり得る。

\begin{align} S ' _ i := \begin{cases} 0 \quad & ( S _ i = 0 ) \cr 1 \quad & ( S _ i \neq 0 ) \end{cases} \cr T ' _ i := \begin{cases} 0 \quad & ( T _ i = 0 ) \cr 1 \quad & ( T _ i \neq 0 ) \end{cases} \end{align}

と定義すれば、 \sum _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) ^ 2 = 0 で判定しても問題ない。 これで \lvert S \rvert \sigma ^ 2 まで削減された。 ちなみに \lvert S \rvert = 1.4 \times 10 ^ 6, \sigma = 26 とするとこの値は 998244353 以下になる。

乱択

素数 P \geq \sigma と一様乱数 r _ i を用いて、 \sum _ i r _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) = 0 \pmod P を判定してもよい。 このとき S の各連続部分列について、マッチしていると誤って判定される確率は 1 / P 以下である。 \sigma が大きくても値域の問題が発生しないことと、項を展開すると 2 つしかないため畳み込みの回数が減るという利点がある。

巡回畳み込みを用いた高速化

これらのアルゴリズム内では、 \sum _ i A _ {k + i} B _ i を各 k について求めるために畳み込みを用いる。 これは B を反転して通常の畳み込みを行えばよいのだが、畳み込んだ結果のうち先頭 \lvert B \rvert - 1 項と末尾 \lvert B \rvert - 1 項は必要がない。 よって巡回畳み込みでこれらの部分が重なっても問題なく、畳み込みの長さを短くすることができる。

線形性を用いた高速化

アルゴリズム中では 2, 3 回の畳み込みを行い、その和だけに興味がある。 よってそれぞれの畳み込みにおいて IDFT を行わず、全部足し合わせて最後に 1 度だけ IDFT を行うことで定数倍高速化になる。 ボトルネックには関係ないと思われるが、IDFT の後の規格化も非零判定だけなので必要ない。

ワイルドカードが一方のみにある場合の高速化

S 側にワイルドカードがない場合、常に S ' _ i = 1 である。 すると \sum _ i S ' _ {k + i} T ' _ i (S _ {k + i} - T _ i) ^ 2 = 0 を積和形にした際に現れる 3 つの項の内 1 つは k に依存しない値になり、その総和は定数となる。 T 側にワイルドカードがない場合も同様の議論により、累積和で 1 つの項は計算できる。 前述した乱択の場合も、 2 つの畳み込みが 1 つに削減される。

\lvert S \rvert \gg \lvert T \rvert の場合の高速化

判定するべき連続部分列のうち最初の \lvert T \rvert 個を判定するためには S の先頭 2 \lvert T \rvert - 1 文字があれば十分であり、これを切り出して今までのアルゴリズムを適用すれば O ( \lvert T \rvert \log \lvert T \rvert) で判定できる。 この調子で \lvert T \rvert 個ずつ判定すると全体で O ( \lvert S \rvert \log \lvert T \rvert) となる。 一度に判定する量は \lvert T \rvert の何倍かの範囲で調整した方が定数倍が良いかもしれない。

実装例

乱択ベース、巡回畳み込みと線形性の高速化あり

https://judge.yosupo.jp/submission/211249

参考文献

[1] Clifford, P., & Clifford, R. (2007). Simple deterministic wildcard matching. Information Processing Letters, 101(2), 53-54.

[2] Clifford, R., Efremenko, K., Porat, E., & Rothschild, A. (2009, January). From coding theory to efficient pattern matching. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 778-784). Society for Industrial and Applied Mathematics.