久しぶりの20時開催という日本人に優しいスケジュールと逃すわけにはいかないと、前日からの風邪を押して*1参加。 DIV1 250 Fox Plaing Game 方針 またウサギ回だ。全部試すと 100 choose 50 でとんでもない組み合わせ数になるので無理。DP だろうなぁ。しか…

(SRM 500 と Codeforces #62 も記録はしてあるので、そのうち載せる)仮眠してから参加。 A Cookies 方針 フラクタルっぽい。これは再帰か、1000はスタック大丈夫かなぁなどと考えているうちに、実は3の冪乗じゃないかと気がつく。 実装 Ruby なら多倍長演算…

A: Irrational problem 方針 やるだけ 実装 Codeforces は Ruby で書くのが常だが、next_permutation が使いたかったので C++ で書いた。 next_permutation するときは、事前のソートを忘れずに! B: Energy exchange 方針 一台あたり エネルギー E にできる…

250 ColorfulRabbits 方針 サンプル見て考える。返答が違うもの同士は絶対に違うグループ。返答が同じなら、同じグループにしてよい。つまり、返答がnなら、そのグループのメンバはn+1。もし、同じ返答をしたウサギが n+1以上いるなら、グループを分割しない…

Codeforces Beta Round #60 C - Harry Potter and the Golden Snitch 方針 vp > vs より、ある時間 t0 で補足可能なら、任意の t >= t0 で補足可能。したがって、二分探索ができる。 実装 実数を扱う問題を解いたのは始めてだったが、非常に難儀した。その分…

仮眠してからスタート。 A Harry Potter and Three Spells 方針 まさかの Harry Potter ネタ。個人的にはナルニア派だけど、ハリー・ポッターも原著で全巻読む程度には好きでした。本質的には、ace < bdf。サンプルを見ると、0 の場合がやっかいそう。いくつ…

Codeforces 62B - Tyndex.Brome 方針 O(n^2)は無理なので、比較元について、各文字の出現する場所をあらかじめ調べておく。例えば、「aは、1,3,10番目に出る」みたいな感じ。比較先の各文字について、上の表を二部探索すればいい。 実装 STL の lower_bound,…