Educational Codeforces Round 29 F. Almost Permutation

想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。

実際、Benqは本番これで通しているらしい

f:id:potetisensei:20200712204017p:plain

 

これを証明する。

問題文中で定義されている目的関数をfとする。これがM凸であることを示す。

まずfの定義域である、実行可能解の集合Sが整基集合（とりあえずM凸関数のステートメントが成立するような集合と考えていい）であることを示す。

 

f:id:potetisensei:20200712211537j:plain

f:id:potetisensei:20200712211547j:plain

↑ノリでm+1にしたけどmでよかったな

f:id:potetisensei:20200712211555j:plain


これはかなり雑、というかこの書き方だと、「対称性からy + e_i - e_jも実行可能解」が成立してないけど、1..nを頂点としたグラフ（辺は、数列の各要素kに関してL[k]からR[k]までの全てのペアに張る）上のpathをイメージするとできることは明らか

 

これさえ証明しておくと、M凸なのは2次関数の和だからかなり自明

f:id:potetisensei:20200712211605j:plain

 

実際これで通る。

https://codeforces.com/contest/863/submission/86645365

多分最悪計算量はO(N^4logN)とか（は？）

な気がする

 

第一回日本最強プログラマー学生選手権予選 F. Candy Retribution

これ1000点じゃないだろ

問題概要

読んで: F - Candy Retribution

解法

条件を満たす昇順の列 \displaystyle{\{A_n\}}に対して、それを並べる方法は\displaystyle{\frac{n!}{\prod_k n_k!}}通りある。 ここで\displaystyle{n_k}は \displaystyle{\{A_n\}}に\displaystyle{k}が\displaystyle{n_k}個含まれることを指す。

よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているものの並べ方の総数」とした時、それをFPSで表わすなら

\displaystyle{ f_k = \left (1 + \frac{1}{1!}yx^ k + \frac{1}{2!}(y x^ k)^ 2 + \ldots \right ) = e^{yx^k} }

として

\displaystyle{ \prod_{k} f_k = e^ {y \sum_{k} x^ k} = e^ {\frac{y}{1-x}} }

となる。 さて、ここに「M番目とM+1番目の値が同一」という条件を追加する。当然これは扱いづらいので、余事象を考えることにする。 すなわち、

\displaystyle{ \sum_{k=1}^\infty \left \{ [y^ M] \left (\prod_{j=k}^\infty f_j \right ) \cdot [y^ {N-M}] \left (\prod_{j=0}^{k-1} f_j - \prod_{j=0}^{k-2} f_j \right ) \right \} }

ここで、\displaystyle{ [ y^ n ] f}は\displaystyle{x, y}に関するFPS \displaystyle{f}の\displaystyle{y^ n}の含まれる項の係数を全て取り出し、\displaystyle{x}に関するFPSを作る操作を指す。つまり、具体的な式として書けば

\displaystyle{ \frac{1}{n!} \frac{d^ n}{d y^ n} f {\bigg|_{y=0}} }

である。さて上記の余事象の式を変形していくと

\displaystyle{ \sum_{k=1}^\infty \left \{ [y^M] e^ {y \frac{x^ k}{1 - x}} \cdot [y^{N-M}] (e^ {y \frac{ 1 - x^ k}{1 - x}} - e^ {y \frac{ 1 - x^ {k-1}}{1 - x}}) \right \} \\ = \frac{1}{M!} \frac{1}{(N-M)!} \sum_{k=1}^\infty \left ( \frac{x^ k}{1 - x} \right ) ^M \cdot \left (\left (\frac{ 1 - x^ k}{1 - x} \right ) ^{N-M} - \left (\frac{ 1 - x^ {k-1}}{1 - x} \right) ^{N-M} \right) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{k=1}^\infty x^ {Mk} \cdot \left (\left ( 1 - x^ k \right ) ^{N-M} - \left ( 1 - x^ {k-1} \right) ^{N-M} \right) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{k=1}^\infty x^ {Mk} \left ( \sum_{j=0}^{N-M} \begin{pmatrix} N-M \\ j \end{pmatrix} (-1)^ j \left (x^ {jk} - x^ {j(k-1)} \right ) \right ) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{j=0}^{N-M} \begin{pmatrix} N-M \\ j \end{pmatrix} (-1)^ j \left (\sum_{k=1}^\infty x^ {M k + j k } - \sum_{k=1}^\infty x^ {M k + j k - j} \right ) }

となる。欲しいのは \displaystyle{ [ y^ N ] e^ {\frac{y}{1-x}} = \frac{1}{n!} \frac{1}{(1-x)^ N}} と上記の式の \displaystyle{L}項目から\displaystyle{R}項目。 \displaystyle{\frac{1}{1-x}}を掛けて累積和を取っておけば、\displaystyle{L-1}項と\displaystyle{R}項の2項を得るだけでよく、上記式をよくにらめば愚直に計算しても調和級数になっているから計算できて、解ける。

これは何？笑

AtCoder Grand Contest 013 E. Placing Squares(+open problem)

問題概要

読んで: E - Placing Squares

解法

とりあえず置いてはいけない箇所の制約を無視する。  

\displaystyle{ f(x) = \sum_{k=1}^ \infty k^ 2 x^ k }
とおけば、置いてはいけない場所がなかった状態での求めるべき値は \displaystyle{\frac{f}{1-f}}の \displaystyle{x^ n}の係数。

\displaystyle{n \geq 1}であるからまあ\displaystyle{\frac{1}{1-f}}としてもよい。 さて、具体的にこの関数の \displaystyle{n}次の係数を \displaystyle{a_n}とすると、

\displaystyle{1-f}のinverseであるから、漸化式 

\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }

となる。まあdpから考えれば自明に出てくる式で、いちいちFPSを経由しなくても良い。

高　　校　　数　　学

さて、上記漸化式が\displaystyle{n}について成り立っている時、命題\displaystyle{C(n)}が成立していると呼称することにする。

\displaystyle{C(n)}と\displaystyle{C(n+1)}が成立しているならば、

\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }
\displaystyle{ a_{n+1} = \sum_{k=0}^ {n} a_k (n+1-k)^ 2 }

である。 2等式を差し引きしてやると、

\displaystyle{ a_{n+1} - a_n = a_n + \sum_{k=0}^ {n-1} a_k (2n-2k+1) }

C(n+1), C(n+2) を仮定すれば

\displaystyle{ a_{n+2} - a_{n+1} = a_{n+1} + \sum_{k=0}^ {n} a_k (2n-2k+3) }

この2等式を差し引きしてやると、

\displaystyle{ \begin{aligned} a_{n+2} - 2 a_{n+1} + a_n &= a_{n+1} - a_n + 3 a_n + 2 \sum_{k=0}^ {n-1} a_k \\ \iff a_{n+2} - 3 a_{n+1} - a_n &= 2 \sum_{k=0}^ {n-1} a_k \end{aligned} }

最終的に、 C(n), C(n+1), C(n+2), C(n+3) を仮定すれば

\displaystyle{ a_{n+2} - 3 a_{n+1} - a_n = 2 \sum_{k=0}^ {n-1} a_k }
\displaystyle{ a_{n+3} - 3 a_{n+2} - a_{n+1} = 2 \sum_{k=0}^ {n} a_k }

より

\displaystyle{ a_{n+3} - 4 a_{n+2} +2 a_{n+1} - a_n = 0 }

が出る。今回は fが綺麗な形をしていたため、このように高校数学をやって出せば終わるが、 そうでない場合はberlekamp-masseyの根幹的なアイデアであるところの、母関数と漸化式の関係を考えて分母を出す必要がある（というより、一旦分かりやすい関数の積に分離+それぞれで高校数学+心温まる手筆算でそれらを合成みたいな感じになる）。

さて、 C(n)を明示的に用いて導出を行ったのは、最終的な漸化式 a _ {n+3} - 4 a _ {n+2} +2 a _ {n+1} - a _ n = 0 が成立するためには、 a _ n, a _ {n+1}, a _ {n+2}, a _ {n+3}の連続する4項について、元の漸化式

\displaystyle{ a_n = \sum_{k=0}^ {n-1} a_k (n-k)^ 2 }

が成立する必要があるということを明確にするためである。 すなわち、この問題の条件として存在している、「 X_k は通ってはいけない」によって強制的に a _ {X _ k} = 0 となっている付近では、 この4項間漸化式は成立しないことを意味する。 逆に、成立するためには直近の4項さえ元の漸化式を満たしていれば良い。 すなわち、それより以前の項がいくつ強制的に定数に書き換わっていても、この漸化式を用いて計算を行って良い。 したがって、 X_k付近以外は行列累乗によって計算できることが分かり、後は X_k 付近を項ごとに O(1) 程度で計算できれば良い。

さて、 X_k 付近については気合で求める。というのも、以下の等式自体は、 C(n), C(n+1) を仮定するだけで言えるのであった:

\displaystyle{ a_{n+1} = 2 a_n + \sum_{k=0}^ {n-1} a_k (2n-2k+1) = 2 a_n + (2n+1) \sum_{k=0}^ {n-1} a_k - 2 \sum_{k=0}^ {n-1} k a_k }

すなわち、 C(n)さえ成立していれば、 C(n+1)を満たす a _ {n+1}は、 a _ kおよび k a _ kの総和さえ保持しているだけで、 O(1)で計算できる。 問題は、 C(n) を満たしていない時である。この時 a _ n = 0 となるわけであるが、

「仮に C(n)が成立していたとすると、 a _ nはいくつであったか」を求めることは上記の行列累乗ないし愚直な計算を用いて可能である。

これを a' _ n とおく。
a' _ n を用いれば、「仮に C(n)が成立していた時、 a _ {n+1} がいくつであったか」も求まる。

これを a' _ {n+1} とおく。すると、元の漸化式を考えた時、 a' _ {n+1} - a' _ n = a _ {n+1}が成立する。よって、このケースにおいても O(1)で計算できる。

さて、残った問題は a _ kおよび k a _ kの総和を保持する必要が生じたこと。これによって行列累乗中でこれらの値についても計算する必要が出てくる。 これは †気合†でやればよい

全部できたので、オッケー

これ、解説の言い換えでやると多分こんな爆発ad-hocクソ面倒行列累乗にはならない気がしていて、 言い換えって大事なんだねーと思ってます。今

Open Problem

結局FPSで定式化しようとしたがうまくいかなかったので方針修正を行った結果かなり遠回しな解法になった。 実はFPSでもある程度までは綺麗な定式化が出来る。 今回は Nが 10^ 9なので最終的にはどうにもならないにしても、 10^ 5オーダーでFPSの操作だけで殴れたら嬉しいに決まっている。 あるいは、 10^ 9オーダーであっても、綺麗にFPSの操作で問題が記述できていれば、高校数学など手計算でちゃんと答えが求まる可能性もある。

困っているのは定式化すると最終的に出てくる方程式が解けないという点。 とりあえずこれについて書いておく。

まず問題を以下の様に一般化する:

問題 石 0, ... , 石 Nが一直線上に並んでおり、カエルが石 0にいる。 カエルは長さ kのジャンプをコスト C _ kで出来る。 石 0から石 Nへいく経路を考える。経路のコストを、行ったジャンプのコストの総積とする。 全ての可能な経路のコストの総和を求めたい。 ただし、石 B _ 1, ..., B _ Mには入ってはならないこととする。

まず、  

\displaystyle{ f(x) = \sum_{k=1}^ \infty C_k x^ k }
とすれば、元の問題と同様に、 B _ iの制約を無視すれば \displaystyle{\frac{f}{1-f}} が可能な移動を表すFPS。 ここで、FPSの作用素（FPSからFPSの写像） D(f)を、「 f中の B _ i次の項のみ取り出す操作」として定義する。 作用素 Dは明らかに線形性・冪等性などを持つ。

今、\displaystyle{\frac{1}{1-f}} 中に含まれる、「本来禁止されていたはずの経路のコスト」を引きたい。

このために、FPS G _ 1, G _ 2, ...を、

\begin{aligned} G _ 1 &= D(f) \\ G _ 2 &= D(f^ 2) - D(f G _ 1) \\ G _ 3 &= D(f^ 3) - D(f G _ 2) - D(f^ 2 G _ 1) \\ ... \end{aligned}

すなわち、

\displaystyle{ G _ k = D(f^ k) - \sum_{i=1}^{k-1} D(f ^{k-i} G _ i) }

として定める。

G _ kは何を表してるかというと、

「 k回のジャンプであって、ぴったり k回目で禁止された場所に移動してしまったもののコストの総和」

である。 これが分かると、 \frac{1}{1-f} G _ kは「 k回目のジャンプで初めて禁止された場所にきてしまった経路全体」を表すことになるので、 これの総和を取って、

\displaystyle{ \frac{1}{1-f} \sum_{k=1}^\infty G _ k }

が求めたい引くコスト全体。

定義式に基づいて、 \sum_{k=1}^\infty G _ kの具体的な値について考えてみると、

\displaystyle{ \sum_{k=1}^\infty G _ k = \sum_{k=1}^\infty D(f ^k) - \sum_{i=1}^\infty \sum_{k=1}^\infty D(f ^k G _ i) }

となっている。 Dの線形性に気をつければ、これは、

\displaystyle{ \sum_{k=1}^\infty G _ k = D(\frac{f}{1-f}) - D(\frac{f}{1-f} \sum_{i=1}^\infty G _ i) }

となる。 G = \sum_{k=1}^\infty G _ kとおくと、

\begin{aligned} G = D(\frac{f}{1-f}) - D(\frac{f}{1-f} G) \\ \end{aligned}

という方程式を満たすような Gが求めたいという問題になる。 G = D(G)に気をつけると、

\begin{aligned} D(G) = D(\frac{f}{1-f}) - D(\frac{f}{1-f} G) \\ \iff D(\frac{G}{1-f}) = D(\frac{f}{1-f}) \end{aligned}

となり、 G = D(G)を満たす（すなわち、 B _ i次の項しか持たないような多項式の）中で、これが成立するような Gを求めたくなる。

これは、 G = \sum_{i} a _ i x ^ {B _ i}とおくと、

\displaystyle{ \sum_{i} a _ i D(\frac{x ^ {B_i}}{1-f}) = D(\frac{f}{1-f}) }

なる \{a _ i\}を求めるのと同値であり、 D(\frac{x ^ {B_i}}{1-f})をそれぞれ求めて、係数をベクトルだと思うことにすると ある種の連立方程式であるということは分かる。 が、 O(n^ 3) 以下の解法があるのか、すなわち、 D(\frac{x ^ {B_i}}{1-f})を列ベクトルとしてもつような行列の逆行列が高速に求められるのかが謎.....

誰か、考えてみてね

追記:

AtCoder Regular Contest 077 F. SS

本質的な補題を証明してから解いたら3時間ぐらいかかった。 解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる？？？ ということで補題と証明を以下に書きます。

補題 \require{cancel} 最小周期 p の長さ n の文字列 S を考え、p \cancel{|} n であるとする。 P = S[0, p)とする。 この時、 S P の 最長borderは P 。すなわち最小周期は n 。

証明

P は明らかに S P のborderであるから、これ以上長いborderがないことを示せば良い。 m = n \bmod pとおけば、正整数 kを用いて、 SP = P^{k} P[0, m) P である。

以下、3ケースに場合分けする。

a) P[m-l, m) P

0 \lt l \leq m として、↑がborderであると仮定する。 k \geq 1 に注意すれば、これは

PP[0, l) = P[m-l, m) P

と同値である。 この等式の両辺の最後の l文字に注目すると

P[0, l) = P[p-l, p)

から p-lは周期。 他方、両辺の l文字目から p-1文字目までに注目すると

P[l, p) = P[0..p-l)

より、 lは周期。 Pの最小周期を wとおいておく。当然、

w \leq min(l, p-l)

が成立する。 \min(l, p-l) \leq \frac{p}{2}であることに気をつけると、そのような lが存在するには、 w \leq \frac{p}{2}が必要。 今、明らかに l + (p-l) \leq p + gcd(l, p-l)であるから、周期性補題から gcd(l, p-l)も周期になる。

これを gとおく。 gも \frac{p}{2}以下であるから、 g, wに対して同様に周期性補題を用いれば、 gは wの倍数である事がわかる。 したがって、 l, p-l, pも全て wの倍数。これは、 Sの周期として wが取れることを意味するから pの最小性に反する。 以上からこのようなborderが取れることはない。

b) kp未満の周期のうち、比較的短いもの

SPが kp未満の周期 w'があると仮定する。すなわち、borderとして

P[l, p) P ... P P[0, m) P

という形になっているものを考える。 この時、 Sも同様に周期 w'を持つことに気をつける。

この w'と pに対して Sに関する周期性補題を適用出来る場合を考える。これがケースb)である。 すなわち

w' + p \leq kp + m + gcd(w', p)

が成立する時を考える。 この時、 p = gcd(w', p)が成立するから w'は pの倍数。

したがって w'に対応するborderは

P...PP[0, m)P

のような形をしている。 borderの最後の p文字について注目すると、suffix側のborderは明らかに Pである。 他方、prefix側は（ P[0, m)の後に続いているわけなので） P[m, p) P[0, m)である。 これは m, p-mの双方が Pの周期であることを表す。よって、ケースa)の議論と同様にして矛盾する。

c) kp未満の周期のうち、長いもの

ケースb)では周期性補題が利用できるほど周期が比較的短い場合には矛盾するということが言えた。 残りは周期性補題の不等式が成立しない場合である。すなわち、

w' + p \gt kp + m + gcd(w', p)

であるケースを考える。 w'は少なくとも、

w' + p \gt kp + m + 1 \iff w' \gt kp + m + 1 - p

より kp+m+2-p以上の長さを持つ。 すなわち、 w'に対応する SPのborderは高々 2p-2程度の長さしか持たない。 よって、borderは

P[p-l,p)P[0,m)P

のような形で表せる（ l+m \leq p-2）。 k = 1 の時、すなわち SP = PP[0,m)Pのように表せる場合は、borderの先頭 l文字および末尾 l文字に注目すると、 l, p-lが Pの周期となりa), b)と同様に矛盾する。

k \geq 2の時、prefix側のborderは PPのprefixである。 したがって、このborderの末尾p文字に注目すると、 l+m, p-(l+m)が Pの周期であることが分かる。 よって、これも同様に矛盾する。

以上で全てのケースを尽くせているから、 S P の最長borderが Pであることが示された。

割と、こうやって場合分けをしないと、borderや周期を考えるまではいいけど、 どのタイミングで P[0,m)にぶつかるかが不透明すぎて頭が爆発すると思っている。 ただ議論自体は全部同じように進むので、もしかしたら慎重に注目する場所と長さを選べば全部ひとまとめで考えられるのかなあ、いやそんなことない気がする

周期性補題って本質的には「周期が十分短いなら最小周期の倍数」って定理なわけだけど、長い周期に関しては何も言えないし、今回は最小周期がとても長いということをいいたいわけなので、それより少しだけ短い周期に関してはこうやって慎重に考えるしかないと思う

AtCoder Grand Contest 018 D. Tree and Hamilton Path

誤読したら解けたんだけど(は？)、未証明が発生した。

問題概要

読んで: D - Tree and Hamilton Path

 

 

解法

まず誤読した問題を書きます:

最長のHamilton Cycleを求めてください。

 

これは多分900点ぐらいです、以下に解法を書くので考えたい人は先に考えてください。

 

 

 

 

 

 

 

 

 

ネタバレ回避用余白

 

 

 

 

 

 

 

 

 

 

 

結論から言うと、任意の頂点から初めて良い以下の再帰で解けます。

gist2e95637586b5bb181112b6d922283ff1

 

sz[v]は適当に根付きにした木のvを根とする部分木のサイズで、mx[v]はvの子が根であるような部分木の最大サイズです。

初めに呼び出すのはdfs(root, root, N)です。

 

これは本来の問題より簡単で、結局「頂点の順列であって、隣り合う頂点のLCAの深さの和が最小になるものを求めてください(順列の先頭と末尾も隣り合っていると見做す)」になって、当然LCAが根であるのが深さが最小であることをなどを考えると貪欲にやっていいことが分かります。

 

次に、誤読したのでここから修正を試みます。

最長のハミルトンサイクルは求まっているので、適当な部分でサイクルを切ってハミルトンパスにすることにします。

未証明なのは、「最長のハミルトンサイクルから取り除ける最短のパスを除いたものは、最長でないハミルトンサイクルから取り除ける最短パスを除いたものより長い」です。証明して助けてください(まあ想定解から示せそうなんだけど、それなら想定解で解けばいいんだから負けだろ)。

 

さて、取り除ける最短パスってなーんだ？実はこれは与えられた木の単一の辺になって、2本以上の辺から成るパスであることはありません。

上の解法が分かった人ならすぐ分かりそうですが一応証明の概略を書きます。

まず求めたのはサイクルなので、適当にシフトしても問題ないです。

ということで先頭をとりあえず根に固定します(根は任意なので実質任意の頂点を先頭に持ってきているのと変わりません)。

この時取り除かれるパスというのは、順列の末尾の頂点と根を端点とするパスです。

つまり引かれる長さは末尾の頂点の深さです。

今、「取り除かれるパスを単一の辺に出来る」ということを示したいので、末尾に持ってきたいのは、根の子です。

上のコードでいうremが-1以下になる時、任意の根の子を末尾に持ってこれます(三角不等式を考えれば言えます)。

そうでない時、mx[v]を与える根の子uは一意に決まります。ここで、mx[v] == N-mx[v]ならば、uは末尾に持ってこれます(これは実はrem == 0と同値です、重心ですね、バーカ)(この時点で、他の子は絶対に持ってこれません。他の子の子孫も持ってこれないので、2辺以上のパスならどうにかなるということもないです)。

そうでない時、末尾に持ってこれるのは、uの子孫の何かのみです。ここで、「持ってこれる頂点の内、最も深さが浅いもの」を持ってきてることにします。これをxとします。

さて、上の解法を理解すると分かりますが、このケースでは、順列のN-1番目もuの子孫になってないとおかしいです(その頂点をyとしましょう)。もっと言えばyはxの子孫として良いです(これはね、多分そう(は？)、xとして持ってこれるものが全て子を持っていないケースはないと思ってるけど、ちょっと自信ない、未証明2)(追記: 末尾に持ってこれる頂点は部分木をなしているはずなので、大丈夫)。なので、もう一度順列を右に1回シフトしてxを先頭、yを末尾に持ってくると、深さが減ります。2辺以上のパスが取り除かれる場合はこうして取り除かれるパスの長さを減らせるので、結局除かれるのは1辺であるということが分かります。

後は「取り除ける1辺の内最短のものを引く」をすれば良くて、これで答えが出ます。

多分そう、だってACしたから。

 

AtCoder Grand Contest 023 B. Find Symmetries

問題概要

B - Find Symmetries

 

解法

NxNの盤面を四方に無限に繰り返し並べて、無限に広がる平面を考えても差し支えない。

ここで、y=x+cの直線をイメージすれば、同じ直線が通るマスは、「良い盤面であるかどうか」が一致する事が分かるので、O(N)個のマスでO(N^2)かけて調べれば十分。