VKCup 2012 Round2

A問題

• SubstringとSubsequece
  • 普通にやるとn^3くらい掛かりそうだけど適当に節約したらn^2に収まった。
  • 書いた。submit。pretest AC。

B問題

• レミングスの問題。
  • ソートして順番に取ってとかあれこれ考えたが分からんから、とりあえず飛ばした。

C問題

• チョコレートがぐるぐる回るらしい。
  • 点がn個ある時に半径rの円で何個の点を覆えるかという問題を平面操作を使ってO(n^2logn)で解くのと似たようなことをすれば解けるはず。
  • 誤差が1e-9とか怖いんでlong doubleを使って実装。submit。pretest WA。
  • Custom Testで調べたらlong doubleを使ってるせいで死んでるっぽいんでdoubleに直してsubmit。pretest AC。

B問題

• やっぱり分からん。
  • 問題文を見なおしていたら、tを二部探索すればいいだけということに気がつく。
  • 普通に書いてsubmit。pretest AC。

E問題

• TLEが心配だけど、AhoCorasickをやるだけに見える。
  • 書いた。submit。と思ったら%lldを使ってたせいで怒られたんで修正してもう一回submit。pretest AC。

結果

oooxx 2672pts 49位 2106→2218
Eはlog消したら通った…。あと赤になった。