Microsoft Q# Coding Contest - Summer 2018
MSのQ#を使った量子コンピューティングのプログラミングコンテスト(本選)。
Microsoft Q# Coding Contest - Summer 2018
週末の3日間で15問を解く。
→練習ラウンド
12完で151位。
量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。
ところどころトリッキーではあるけれど難しすぎるというほどでもない。(Q#歴0日から始めた割に善戦したが全完したかった)
公式Editorialはこちら。
続きを読む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)