らての精進日記

修行をします

形式的冪級数についてのアレコレ

こんにちは


ここ数週間、形式的冪級数について勉強しています。

形式的冪級数は、理論的に興味深い対象である一方で、組み合わせ論などに応用できます。実際、競技プログラミングにおいて、

・直接的に形式的冪級数を使うことが想定された問題
・形式的冪級数以外の解法(例えばdpなど)を使うことが想定されているが、形式的冪級数の世界で考えると見通しが良い問題
・よくわからないけど形式的冪級数ライブラリで殴ると終わる問題


などが出題されています。

僕自身、あまり理解は深くありませんが、学習の過程で得られた知見などを共有していけたらいいなと思っています。


最終的には、体系的な資料をpdfなどの形式で作成して配布できたらいいなと考えていますが、今はまだ試行錯誤の段階なので、dropbox paperに書き殴っています。


このブログ記事に、作成したdropbox paperのdocumentへのリンクや、今後の執筆の展望などをまとめていこうと思うので、よろしくお願いします。


本執筆活動の目的は、競技プログラミングにおける形式的冪級数を用いた解法を紹介し、また、解法の正当性を明らかにしていくことです。


導入記事:
paper.dropbox.com
かなり基本的なこと(定義や、最低限の性質の紹介・証明)を書いています。
内容はかなり易しいですが、読んでいて楽しいものではないと思います。
もう少し簡潔に(ある程度自明と思えることや、無味乾燥とした長い証明については、ページをわけるなど)していけたらなと思います。

無限和と代入:
まだ書いてません。早く書きましょう。
形式的冪級数の代入という概念は、かなり複雑で曖昧な概念だと思えるのですが、形式的冪級数の無限和を真面目に定義して、ちゃんとやると、簡単なことであると気付きます。

微分積分
まだ書いていません。早く書きましょう。
形式的冪級数微分積分は、かなり直観的で簡潔な形で定義されます。しかし、ここで定義された微分積分は、解析学におけるそれと類似した性質を持つことがわかり、強い道具となります。

形式的冪級数におけるlogについての思考:
paper.dropbox.com
タイトルの通りです。まだ完成していません。かなり見当違いのことが書いてあると思いますが、気にしないでください。ある程度理解が進んできたので、近いうちにちゃんと書きます。代入や微分積分について勉強していないと内容をしっかり追えないと思うな

形式的冪級数の各種演算のアルゴリズム
まだ書いてません。早く書きましょう。
和や差については、言うまでもないでしょう。
積については、高速多項式乗算が行えるような代数系(複素数体や、有限体など)については、O(nlogn)でできます。
積の逆元についても、O(nlogn)のアルゴリズムがあります(ニュートン法を用いるもの)


代入は、一般にはO( (nlogn)^1.5)のアルゴリズムが、知られているなかで最速だと思います(多分ね)
しかし、特別な場合にO(nlogn)でできて、例えばexp(x)に代入するのは高速にできます(これはかなり重要な操作です)

logは、具体的な計算式が導出されるので、それに従って計算します。これもO(nlogn)です。

平方根については、ニュートン法を用いたアプローチが知られていますが、実はlogとって2で割ってexpに代入するだけで計算できると思います。一般に、P(x)^nやP(x)^(1/n) (n:自然数)は、logとってnをかけたり割ったりしてexpすれば求まると思います。これもたまに使えます。

ラグランジュの反転公式:
まだ書いてません。早く書きましょう。
en.wikipedia.org
上記のwikipediaの記事にあるように、複素関数論において上記のような定理が成り立ちます。この結果をそのまま形式的冪級数の計算に使うと、実数体(あるいは複素数体)を係数とする形式的冪級数の計算を、(収束半径が0でないなら)解析学を流用してできちゃったりします。しかし、この定理は、(形式的ローラン級数を導入したりすると)形式的冪級数の世界で類似の定理に書き直すことができて、収束半径などを気にする必要がなくなります。(これ認識合ってるかな 主張自体はあってる気がするけど、解釈はあまりよろしくないかもね)


形式的冪級数を用いた解法について:
まだ書いてない


1/(1-x)をかけまくったりするような基本的なやつから、expに代入したり、代数方程式を解いたり、微分方程式を解いたり(これは見たことない(は??))  、ラグランジュの反転公式を使ったり(これは見たことある。かなり強い定理です) ベルヌーイ数をO(nlogn)で列挙してみたり、多変数形式的冪級数に対してラグランジュの反転公式使って偏微分してなんかするやつ(謎)をやったりします。ほかにもたくさんあると思いますが、少しづつまとめていけたらいいね



まだほとんど書いてないですが、急いで書きたいです。アドバイスや鋭い指摘待ってます。

codechef:PSUM

問題を解く過程で考えたことを書くよ

題意

Contest Page | CodeChef


N個の宝がある
i番目の宝の重さはciで、価値はviである
重さSまで許容するナップザックがある

ナップザックに収まるような(重さの合計がSを越えないように)宝の選び方すべてについて、(価値の合計)^Kを計算して、その総和を求めてください mod 998244353

N,S<=100
K<=100
ci<=100
vi<=10^9

考え方

前からdpしていくイメージで考える

今、[1,i-1]の中からいくつか選んで、その価値の総和がvであるとする。そして、v^Kが求まっているとする

このとき、(v+vi)^Kを計算できると嬉しい(i番目の宝を追加したときの価値^K)
二項展開すると、(v+vi)^K=Σbinom(K,k)v^k vi^(K-k)
あ、exponential generating functionの積が計算できればいいじゃん
→modが998244353 勝ちました


負けました
www.codechef.com


上記の解法について詳しく書くと、
dp[i][j][k]:=宝を[1,i]から選んで、重さの総和がjとなるようなすべての選び方についての、価値^kの総和
と定義すると、二項展開の式から、
dp[i][j][k]=dp[i-1][j][k]+ Σ[l=0,...,k] binom(k,l)dp[i-1][j-ci][l]*vi^(k-l)
という漸化式が生えて、これはO(NSK^2)で計算できる
ここで、漸化式をよく見るとexponential generating functionの積を計算するような形になっている gg




上記をさらに詳しく説明すると、
2つの数列{ai},{bj}があったときに、新たな数列
{ck} (ck=Σ[l=0,...,k] binom(k,l) ai*b
数式を普通に打ち込んだら読みにくいだろ やめました

JAG夏合宿2019参加記

参加しました

day1

担当した問題と、印象に残った問題について書きます
C:
やりまーす

D:
法が互いに素でないような連立合同式を解けばいい
ライブラリの使い方が分からなくてチーム全員大慌てでしたが、冷静になると、ベズーの等式を考えて拡張ユークリッドの互除法でささっと求解できるようなスマート人間になるべき


F:
これすごいですね 感動です

G:
こういう問題楽しいですね
明らかにdpなのはわかって、dpを成立させるために必要な状態の持ち方を考えていきます

H:
writer許さね~~~~~~~という気持ちになるんですが、こういう問題を堅実に実装できるようにならないとダメだな(気づき)

I:
ゾンビを基準とした相対位置・相対速度を考えるとかなり見通しがよい
人間について二分探索することにすると、普通にCHTになって終わり
しかしライブラリの仕様が分からず大幅にタイムロスした グッと睨むと蟻本ベースだとわかるので直線の追加の方向が理解できて終わり

上記のlogが2つの解法でギリギリ通ったんですが、並列二分探索すればCHTは線形のものを使用できてlogが減ります これが想定なのかな

J:
うん
ぽてちくんがフローを使う嘘を考えたんだけど、反省して議論してたら二部マッチングでよいとわかり、写経したフローが生きる 不死鳥 


K:
どう見ても2D Convolutionで、破滅

2D Convolutionがまともに解けるのは知っていたが、知識がないと無理だと思ってまともに考察しなかった 反省

wikipediaとか見てると、2Dの離散フーリエ変換を行列で表してみたらうれしい性質がある(2Dの離散フーリエ変換は、各行を離散フーリエ変換してから各列を離散フーリエ変換すればよい)ことがわかって、知見でした  

HIR180先生に、直接的に1D Convolutionに落とす方法を教えてもらって、嬉しい

総評:
時間かければ確実に解けるレベルの問題に時間をかけてしまっているところがある

ギア上げて素早く処理していきたいね 

day2

writer側です。いかがでしたか?僕が書いた問題を当ててみてください。一問も書いてません ぽてちくんごめんなさい

B:
こんなん無理だろ
C:
最小費用流に落ちるのはまあわかる(実はそこまで正当性をはっきり理解できていないが)

貪欲はよくわからん

F:
そういえばいまだに一般マッチング書いたことありません 理解もしてないし 詰んだ

G:
これかなり難しいと思うけどな でもsigmaroonはあっさり通している なぜ

H:
形式的冪級数で解けます(ホントかな??)


まあ愚直dpしてみるとかなり分かりやすい形になって、エスパーするなり組み合わせ的にイメージするなりdp配列を多項式で表現してみたりすると二項係数が出てくると思う

見た目は威圧的だけど考察はやりやすいと思うな

I:
これ絶対やりたくねえな アレルギーが出ます

J:
まあある程度分かりやすい式にはなって、計算方法が問題になる
ダブリングしながら多項式補間する方法普通に素敵だとおもった

総評:
ぽてちすごい

酒は飲んでも飲まれるな
人に迷惑をかけるな
酒を飲むな

やむなくさんごめん(いなかったけど)(他に謝るべき人いるだろ)

day3

C:
頭が悪いので貪欲に確信を持てない 実装も怖い よくわからないことはぽてちにやらせよう

D:
iとi xor Xはどちらか片方しか使ってはダメで、ここから2-SATが芽生える
3^nでダメなペアを列挙できるのはまあ難しくなくて、本当に難しいのは、なぜか2-SATをUFでやり始めたこと(無向辺ではありませんが??)

2-SATではSCCを用いるという事実を唐突に思い出して、焦りました

E:
なんかぽてちとreewが頑張ってたな 

F:

こういう問題見ると頭止まっちゃう 存在意義なし 赤コーダーとは

G:
英語が読めなさ過ぎて、"On the i-th operation, flip a fair coin"を読んだときに、木の頂点にコインが置いてある問題だと思っちゃって一生読解が進まなくなったな(どうして?)

みんなEやってたから邪魔しづらかったんだけど、勇気を出してぽてちに英語読んでもらえばよかったな 

問題自体は面白いと思います(題意が分かれば解けてたと思う(負け惜しみ))

H:
UFをマージすれば解けるけどなあ~~(思考停止)
UFをマージすれば解けるじゃん(天地開闢)(国士無双)

残り15でPCが開いたので書いたけどダメだった 主人公ではないので


I:
解けぬ
解説みても解けない

J:
なんかreewとぽてちが通したな なんで

総評:
だめ

おわりに

競技プログラミングをやりましょう

日記 20190316

卒業した

3/15に卒業式でした 朝まで飲んでから家に帰って寝て起きてバイトに行きました 3/16終わり。

ポエム

"みんなやってることをやらないこと" "周りと波長が合わないこと"をかっこいいと思っていた。
わざわざ学校をさぼって、学校の真横にあるパン屋で確率統計の本を読んでいる自分に酔っていた。
卒論提出が近いのに研究室に行かずに家でゲームやってる自分に満足していた。
いつの間にか自分しか見えなくなっていたと思う。周りに大切な人がたくさんいたのにね。大変お世話になりまさした!!やるな笑笑

2019/5/6追記:ポエム書くな

フォートナイトについて

やっぱりミドルセンシじゃないとエイムが合わないな 無理にローセンシでやってたけど戻したらまともになった

ポエム

時間経つの早くてびっくりする もっと毎日大切にしたい

趣味とか

競技プログラミングをちゃんとやろうと思います フォートナイトも楽しいけどね
新しい趣味を探しつつ、昔の趣味も大切にしたいな 
そういえばルービックキューブとか全然やってないな 

星見純那について

すき

日記 20180923

日記毎日書けや

競技プログラミング

opencupに出た チームメイトが強すぎてお荷物になることに成功した 大変うれしく思います。

フォートナイト

ちゃんとご飯食べないと調子でないことに気付いた 食べよう ごはん
とくに成長なし でも楽しい ゲームって、いいなあ

漫画

進撃の巨人全巻読んだ(一昨日ね) そのせいで徹夜でバイトに行きました(昨日ね) 日記は今日のことを書くんやで

デスノートの7巻までを読み返しました 文字が多い
やがきみ、よさ

少女歌劇 レヴュースタァライトについて

双葉と香子、いいな ストーリーにほとんど関わってこない(極端な言い方をすると6話以外に登場していない)けど別にそれでいいと思う 6話で起承転結すべて見られたし本当に満足

西條クロディーヌと天堂真矢、非常にいいな 尊さの原因は百合ではない気がする(百合でもいいけど) ここにしかない独特で貴重な人間関係(友情でもない気がする なんだろう)が本当に素晴らしくて、したがって、次の手順を実行する
1.西條クロディーヌと天堂真矢を主人公にする
2.アニメを100クール制作する

西條クロディーヌだけオリジナルのレヴュー曲がない気がする 

じゅんなななも非常にいい ストーリーの本流における役割が事務的(純那→レヴューの導入役 ばなな→レヴューの裏側の紹介役)な感じなのが寂しいところではあるけれども、9話の最後好き

まひるちゃんもよくて、何がいいかというと5話のレヴュー曲が本当にいい

ひかりちゃんについてはちょっと難しい 4話まで見た限りだと完全に挙動不審で、なんやこいつとなっていた(伏線のために挙動不審な行動が見え隠れするのは別にいいんだけど、ひかりちゃんに関しては本当にすべて挙動不審で、うくにきあくんかと思った)
ただ、8話以降は好感度かなり上がった(純粋に再生産シーンが好きだし、終盤の強さにも納得がいくので)

華恋ちゃん 4話で気持ちを新たにして強くなったという設定だと思うんだけど、何が変わったのかよくわからない(熱心に練習するようになったからといっていきなりクロディーヌに勝てるようになるのか?)(まあ技術ではなくきらめきで勝負しているのだと思うと、練習時間ではなく練習態度が重要なのかもしれない) もっと時間をかけて段階的に成長していく過程を描いてほしかった感がある その方が感情移入しやすかったかなあ 
でも10話の最後の歌声と11話での主人公感によって好感度が上がってきている

ウクニキアくんについて

胡桃沢=ウクニキア=マクドウェルって555なんだよね ところで、俳句は575なんだよね これがなにを意味しているかというと、ウクニキア様が世界を掌握した暁には日本の俳句は555がスタンダードになるということ。

追記:"ウクニキア様が世界を掌握したら当然ウクニキア様と呼ぶべきなので胡桃沢=ウクニキア様=マクドウェルなので575では"とのご指摘をいただきました。この意見を大変重く受け止め、再発防止に努めたいと思います。

文章力について

括弧を多用しすぎじゃないか 読みづらい

今日はどうでしたか

どうしようもないね

日記 20180920

日記 書いていきたいと思います 

競技プログラミング

ACPC day2 バイトで出られず やめてえ

ACPC 人々が飲み会をしている いきてえ

ACPC writerをブロックするの やめなさーい!
(作詞:らて 作曲:菅野よう子)

バイト

レジ打ち ストレスやばいね 

漫画とか

進撃の巨人の23から26までを買いました めっちゃ面白いよ
あとやが君の5巻買った よんでないよ

フォートナイト

初めて配信した 人に見てもらうの楽しいんだけど恥ずかしい 人間って、不思議だな

人生

ファミマのトルティーヤおいしい でも400円 おひるごはんにしては少ない
いつか大金持ちになったらバイト前の朝食としてトルティーヤとコーヒー買いてえ

人生2

人と接する機会がなくて寂しい うくにきあくん、ねねにきあくん、遊びませんか びーとくんはいいや

人生3

お酒飲むと酔う バイトの後はすぐにお風呂で温水を浴びて体をほぐさないとフォートナイトしちゃだめですよ これはフォートナイトの欄に書きなさい

レヴュースタァライトについて

10話また見た 西條クロディーヌよすぎないか 彼女の純粋な心を思うと胸が熱くなる

うくにきあくんおいしかった?笑

うん

今日は楽しかった?笑

ふつう