Microsoft Q# Coding Contest - Summer 2018 - Warmup
MSのQ#を使った量子コンピューティングのプログラミングコンテスト（の練習ラウンド）。
Microsoft Q# Coding Contest - Summer 2018 - Warmup
→本選
Mac*1に環境入れるのとか面倒で、Warmupラウンドをやってたのは知ってたけどスルーしてた。
本戦開始まで2時間切ったあたりで急にやる気になったので、Visual Studio CodeとQ#環境をセットアップして、過去問のWarmupに本戦前にいくつか投げてみた（とりあえず6AC+1WA）。
Warmupというだけに、チュートリアルっぽい問題が並ぶ。
Q#触るのは今回が初めてだけど
- H（アダマール）ゲートは
H() - CNOTゲートは
CNOT() - Xゲートは
X() - 計測は
M()
とか、そのまんまなので書きやすい。
【追記】本戦の途中ですがwarmup全完（7/8 13:14）
*1:只今修理入院中につきレンタル代替機を使用中
高速ゼータ変換／高速メビウス変換
高速ゼータ変換・高速メビウス変換が気になっていたところにタイムリーに先日の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を埋めていった。
これで現行のスコア体系になってからの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
MathMash Round 19
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:動かすには何箇所か修正が必要
