高速ゼータ変換／高速メビウス変換

高速ゼータ変換・高速メビウス変換が気になっていたところにタイムリーに先日のARC 100のE問題が来て（ちゃんと解けなかったので）折角なのでこの機会にマスターしようと思い競プロ有識者の皆さんのブログやツイートを漁ってみました。

• はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
• 高速ゼータ変換 - とどの日記
• 高速メビウス変換について - lan496の日記
• https://pekempey.hatenablog.com/entry/2016/10/30/205852
• ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
• 競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん
• 高速ゼータ変換、高速メビウス変換 - omochan's diary
• 競技プログラミングをするフレンズ on Twitter: "ギンギツネ「ちょっと調べてみたけど、高速ゼータ変換は「S⊂TなるTに関する和」を求める操作みたいね。今回みたいに「T⊂SなるTに関する和」を求める操作は高速メビウス変換って言うらしいわ」"
• 昼休みにAPを消化しろ on Twitter: "俺は「Sに対して、S⊂Tである全てのTに渡る和」を求めるのをゼータ変換、その包含関係が逆になった「T⊂Sである全てのTに渡る和」を求めるのがメビウス変換、メビウス変換の逆変換をメビウス逆変換と呼んでるんのだけど、競プロ界隈ではメビウス逆変換のことをメビウス変換と呼んでいるらしい"

・・・・・・

ゼータ変換／メビウス変換が互いに逆変換の関係なのはわかったんだけど…どっちがどっち？

というか、4種類あるんだけど…どれがどれ？

ABC A/B問題のWA原因リスト

水曜深夜の比屋定先輩タイムまですこし時間を持て余したので、ABCの不出場回のA/B問題*1を埋めていった。

• 使用言語: Python2 (2.7.6)*2
• エディタ: 問題ページのフォームに直接書き込み*3

これで現行のスコア体系になってからのABCはD問題1つ*4を残して全部埋まったので、明日からARCのE問題以降に取り組める（取り組まざるを得ない）。

解いた問題の解法の詳細はここには書かないが、代わりにWAやREを出した問題で何故WAを出したのかを列挙してみる。
AtCoder ProblemsのSubmissions一覧からWAを出した物のdetailsを見て、提出コードだけから（問題は見ずに）WAの原因を思い出していった。結構覚えているものだ。

*1:AtCoder Scoresに載っているもののみ、現行のスコア体系になる以前の回は対象外。で97問残ってた

*2:いまだにpython3より2の方が書き慣れている

*3:サンプルケースでのテストはほとんどしていない

*4:ABC050 D - Xor Sum

〈メモ〉AtCoderでnumpyを使う

ABCのA,B問題埋めをpythonでやってて
AtCoderはnumpyが使えることを知ったのでメモ

ABC 047 B - すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit) (200)

（問題文はこちら）

MathMash Round 19

www.mathmash.org

6/11 2:25-4:25am JST
https://www.mathmash.org/contest.php?id=19

ABCの後に寝落ちして、ちょうど目が覚めたところでTLで目に飛び込んできたので（急遽アカウントを作って）出てみた
7完 (ABCDEF-H) 9816点で8位
↑EとHはズルしてる
1248(+248)

DFT（離散フーリエ変換）とNTT（数論変換：整数（剰余環）を用いたDFT）

先日ARC埋めの一環でATC001のC問題（高速フーリエ変換）を解いたのだけれど、こういう畳み込み問題はDFT（discrete Fourier transform；離散フーリエ変換）の代わりに NTT（number-theoretical transform；数論変換）という "整数（剰余環）を用いたDFT" でも解けるらしい。

そこで、math314氏の「 任意modでの畳み込み演算をO(n log(n))で - math314のブログ」の解説と実装例*1を追いながら自分で実装して試してみた。こないだcomplex<double>で自分で書いてみたやつ（→ATC001）とほぼ同じことをしているように見える。これは面白い。

（ここでは解説はしないので、詳しくはmath314氏の元記事を参照して頂ければと思います）

*1:動かすには何箇所か修正が必要

Kindle Oasis（第9世代）を買った話

我が家にKindle Oasis（第９世代）がやってきました。

Amazonさんから黄色復帰祝いが届いた pic.twitter.com/1KDMun8OJc

— naoya t (@naoya_t) 2018年6月3日

TopCoder Algoのレーティングが黄色に復帰した後に届いたので黄色復帰祝っぽくなりましたが、ぽちった時点ではそういうイベントが来るのは予期していませんでした。

例題で学ぶ微分方程式：1.1 常微分方程式と相図

なんとなく「時代は微分方程式だよなあ」と思って先日オライリーの「例題で学ぶ微分方程式」を買いました。
www.oreilly.co.jp

本書ではMathematicaでプログラムが書かれているので、これをPythonでというかJupyter notebook (scipy+matplotlib) で置き換えながら読み進めようと思います。

というか、jupyter notebookをgist経由でブログに埋め込むテストです。