naoya_t@hatenablog

いわゆるチラシノウラであります

中央値の中央値 (median of medians)

Algorithms

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。
〜
厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい（or 大きい）値が存在することが示せる。

真のmedianの近似として、適当なpivotの選択に使える。
（配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど）

原理は割と簡単

続きを読む

期待値の線形性（が腑に落ちるまでの長い軌跡）

Mathematics Algorithms 過去問

「期待値の線形性」について、けんちょん先生やふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。（随時加筆修正）

期待値の線形性そのもの
$$ \mathbb{E}[ax+b] = a\mathbb{E}[x] + \mathbb{E}[b] $$
は分かってるし、「\mathbb{E}[\sum f(x)] の形で書けるものは\sum\mathbb{E}[f(x)] に書き換えて解ける」という事実にも別に疑問はない。というか、

f(x) is 何

という式が（都合よく）立てられる問題なのかを判別できるかどうかとか、式が立てられたとしても前後の文脈を無視して計算しても大丈夫なのか（どうも気持ち悪いし納得しづらい）とかいう話か。

続きを読む

Microsoft Q# Coding Contest - Summer 2018

Codeforces 量子力学&量子計算 Programming Contest

MSのQ#を使った量子コンピューティングのプログラミングコンテスト（本選）。
Microsoft Q# Coding Contest - Summer 2018
週末の3日間で15問を解く。
→練習ラウンド

12完で151位。
量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。
ところどころトリッキーではあるけれど難しすぎるというほどでもない。（Q#歴0日から始めた割に善戦したが全完したかった）

f:id:n4_t:20180710024132p:plain:w500
f:id:n4_t:20180710042715p:plain:w500

公式Editorialはこちら。

続きを読む

Microsoft Q# Coding Contest - Summer 2018 - Warmup

Codeforces 量子力学&量子計算 Programming Contest 過去問

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）
f:id:n4_t:20180708132416p:plain:w500

*1:只今修理入院中につきレンタル代替機を使用中

続きを読む

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

Algorithms Mathematics

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

・・・・・・

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

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

続きを読む

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

AtCoder 過去問

水曜深夜の比屋定先輩タイムまですこし時間を持て余したので、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を使う

AtCoder NumPy Python 過去問

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

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

（問題文はこちら）

続きを読む