Educational Codeforces Round 29 F. Almost Permutation
想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。
実際、Benqは本番これで通しているらしい
これを証明する。
問題文中で定義されている目的関数をfとする。これがM凸であることを示す。
まずfの定義域である、実行可能解の集合Sが整基集合(とりあえずM凸関数のステートメントが成立するような集合と考えていい)であることを示す。
↑ノリでm+1にしたけどmでよかったな
これはかなり雑、というかこの書き方だと、「対称性からy + e_i - e_jも実行可能解」が成立してないけど、1..nを頂点としたグラフ(辺は、数列の各要素kに関してL[k]からR[k]までの全てのペアに張る)上のpathをイメージするとできることは明らか
これさえ証明しておくと、M凸なのは2次関数の和だからかなり自明
実際これで通る。
https://codeforces.com/contest/863/submission/86645365
多分最悪計算量はO(N^4logN)とか(は?)
な気がする
第一回日本最強プログラマー学生選手権予選 F. Candy Retribution
これ1000点じゃないだろ
問題概要
解法
条件を満たす昇順の列 に対して、それを並べる方法は通りある。 ここでは にが個含まれることを指す。
よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているものの並べ方の総数」とした時、それをFPSで表わすなら
として
となる。 さて、ここに「M番目とM+1番目の値が同一」という条件を追加する。当然これは扱いづらいので、余事象を考えることにする。 すなわち、
ここで、はに関するFPS のの含まれる項の係数を全て取り出し、に関するFPSを作る操作を指す。つまり、具体的な式として書けば
である。さて上記の余事象の式を変形していくと
となる。欲しいのは と上記の式の 項目から項目。 を掛けて累積和を取っておけば、項と項の2項を得るだけでよく、上記式をよくにらめば愚直に計算しても調和級数になっているから計算できて、解ける。
これは何?笑
AtCoder Grand Contest 013 E. Placing Squares(+open problem)
問題概要
読んで: E - Placing Squares
解法
とりあえず置いてはいけない箇所の制約を無視する。
とおけば、置いてはいけない場所がなかった状態での求めるべき値は の の係数。であるからまあとしてもよい。 さて、具体的にこの関数の 次の係数を とすると、
のinverseであるから、漸化式
となる。まあdpから考えれば自明に出てくる式で、いちいちFPSを経由しなくても良い。
高 校 数 学
さて、上記漸化式がについて成り立っている時、命題が成立していると呼称することにする。
とが成立しているならば、
である。 2等式を差し引きしてやると、
を仮定すれば
この2等式を差し引きしてやると、
最終的に、を仮定すれば
より
が出る。今回はが綺麗な形をしていたため、このように高校数学をやって出せば終わるが、 そうでない場合はberlekamp-masseyの根幹的なアイデアであるところの、母関数と漸化式の関係を考えて分母を出す必要がある(というより、一旦分かりやすい関数の積に分離+それぞれで高校数学+心温まる手筆算でそれらを合成みたいな感じになる)。
さて、を明示的に用いて導出を行ったのは、最終的な漸化式 が成立するためには、の連続する4項について、元の漸化式
が成立する必要があるということを明確にするためである。 すなわち、この問題の条件として存在している、「 は通ってはいけない」によって強制的に となっている付近では、 この4項間漸化式は成立しないことを意味する。 逆に、成立するためには直近の4項さえ元の漸化式を満たしていれば良い。 すなわち、それより以前の項がいくつ強制的に定数に書き換わっていても、この漸化式を用いて計算を行って良い。 したがって、 付近以外は行列累乗によって計算できることが分かり、後は 付近を項ごとに 程度で計算できれば良い。
さて、 付近については気合で求める。というのも、以下の等式自体は、を仮定するだけで言えるのであった:
すなわち、さえ成立していれば、を満たすは、およびの総和さえ保持しているだけで、で計算できる。 問題は、 を満たしていない時である。この時 となるわけであるが、
「仮にが成立していたとすると、 はいくつであったか」を求めることは上記の行列累乗ないし愚直な計算を用いて可能である。
これを とおく。
を用いれば、「仮に が成立していた時、 がいくつであったか」も求まる。
これを とおく。すると、元の漸化式を考えた時、 が成立する。よって、このケースにおいてもで計算できる。
さて、残った問題はおよびの総和を保持する必要が生じたこと。これによって行列累乗中でこれらの値についても計算する必要が出てくる。 これは †気合†でやればよい
全部できたので、オッケー
これ、解説の言い換えでやると多分こんな爆発ad-hocクソ面倒行列累乗にはならない気がしていて、 言い換えって大事なんだねーと思ってます。今
Open Problem
結局FPSで定式化しようとしたがうまくいかなかったので方針修正を行った結果かなり遠回しな解法になった。 実はFPSでもある程度までは綺麗な定式化が出来る。 今回はがなので最終的にはどうにもならないにしても、オーダーでFPSの操作だけで殴れたら嬉しいに決まっている。 あるいは、オーダーであっても、綺麗にFPSの操作で問題が記述できていれば、高校数学など手計算でちゃんと答えが求まる可能性もある。
困っているのは定式化すると最終的に出てくる方程式が解けないという点。 とりあえずこれについて書いておく。
まず問題を以下の様に一般化する:
まず、
とすれば、元の問題と同様に、の制約を無視すれば が可能な移動を表すFPS。 ここで、FPSの作用素(FPSからFPSの写像)を、「中の次の項のみ取り出す操作」として定義する。 作用素は明らかに線形性・冪等性などを持つ。今、 中に含まれる、「本来禁止されていたはずの経路のコスト」を引きたい。
このために、FPS を、
すなわち、
として定める。
は何を表してるかというと、
「回のジャンプであって、ぴったり回目で禁止された場所に移動してしまったもののコストの総和」
である。 これが分かると、は「回目のジャンプで初めて禁止された場所にきてしまった経路全体」を表すことになるので、 これの総和を取って、
が求めたい引くコスト全体。
定義式に基づいて、の具体的な値について考えてみると、
となっている。の線形性に気をつければ、これは、
となる。とおくと、
という方程式を満たすようなが求めたいという問題になる。 に気をつけると、
となり、を満たす(すなわち、次の項しか持たないような多項式の)中で、これが成立するようなを求めたくなる。
これは、とおくと、
なるを求めるのと同値であり、をそれぞれ求めて、係数をベクトルだと思うことにすると ある種の連立方程式であるということは分かる。 が、以下の解法があるのか、すなわち、を列ベクトルとしてもつような行列の逆行列が高速に求められるのかが謎.....
誰か、考えてみてね
追記:
なってない崎
— 精進 (@shojin_comp) December 16, 2019
B_iが等差数列みたいな制約があったら、divを使っていい感じで求められるということはわかった崎
AtCoder Regular Contest 077 F. SS
本質的な補題を証明してから解いたら3時間ぐらいかかった。 解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる??? ということで補題と証明を以下に書きます。
証明
は明らかに のborderであるから、これ以上長いborderがないことを示せば良い。 とおけば、正整数を用いて、 である。
以下、3ケースに場合分けする。
a)
として、↑がborderであると仮定する。 に注意すれば、これは
と同値である。 この等式の両辺の最後の文字に注目すると
から は周期。 他方、両辺の文字目から文字目までに注目すると
より、は周期。 の最小周期をとおいておく。当然、
が成立する。 であることに気をつけると、そのようなが存在するには、が必要。 今、明らかにであるから、周期性補題からも周期になる。
これをとおく。 も以下であるから、に対して同様に周期性補題を用いれば、はの倍数である事がわかる。 したがって、も全ての倍数。これは、の周期としてが取れることを意味するからの最小性に反する。 以上からこのようなborderが取れることはない。
b) 未満の周期のうち、比較的短いもの
が未満の周期があると仮定する。すなわち、borderとして
という形になっているものを考える。 この時、も同様に周期を持つことに気をつける。
このとに対してに関する周期性補題を適用出来る場合を考える。これがケースb)である。 すなわち
が成立する時を考える。 この時、が成立するからはの倍数。
したがってに対応するborderは
のような形をしている。 borderの最後の文字について注目すると、suffix側のborderは明らかにである。 他方、prefix側は(の後に続いているわけなので)である。 これはの双方がの周期であることを表す。よって、ケースa)の議論と同様にして矛盾する。
c) 未満の周期のうち、長いもの
ケースb)では周期性補題が利用できるほど周期が比較的短い場合には矛盾するということが言えた。 残りは周期性補題の不等式が成立しない場合である。すなわち、
であるケースを考える。 は少なくとも、
より以上の長さを持つ。 すなわち、に対応するのborderは高々程度の長さしか持たない。 よって、borderは
のような形で表せる()。 の時、すなわちのように表せる場合は、borderの先頭文字および末尾文字に注目すると、 がの周期となりa), b)と同様に矛盾する。
の時、prefix側のborderはのprefixである。 したがって、このborderの末尾p文字に注目すると、がの周期であることが分かる。 よって、これも同様に矛盾する。
以上で全てのケースを尽くせているから、 の最長borderがであることが示された。
割と、こうやって場合分けをしないと、borderや周期を考えるまではいいけど、 どのタイミングでにぶつかるかが不透明すぎて頭が爆発すると思っている。 ただ議論自体は全部同じように進むので、もしかしたら慎重に注目する場所と長さを選べば全部ひとまとめで考えられるのかなあ、いやそんなことない気がする
周期性補題って本質的には「周期が十分短いなら最小周期の倍数」って定理なわけだけど、長い周期に関しては何も言えないし、今回は最小周期がとても長いということをいいたいわけなので、それより少しだけ短い周期に関してはこうやって慎重に考えるしかないと思う
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
問題概要
解法
NxNの盤面を四方に無限に繰り返し並べて、無限に広がる平面を考えても差し支えない。
ここで、y=x+cの直線をイメージすれば、同じ直線が通るマスは、「良い盤面であるかどうか」が一致する事が分かるので、O(N)個のマスでO(N^2)かけて調べれば十分。