Maximum-Cup 2008

初参加

A

やるだけな問題

B

ただのダイクストラ…
なのに、問題文読み落としまくってWA×3orz
これがさいたまトラップかー

C

ビットDP
最初グループ数決まってるの忘れてて2^18*18^2なら余裕だなと思っていたけど、グループ数入れたら2^18*18^3になってしまった
まにあわねーと思いつつ提出したら間に合ったｗ

D

やるだけな問題
thEとかaNとかあったらどうなんだろうと思ったけど、特に気にせずやったら一発で通った

E

謎

F

むずいー
O(N^2)のしか思いつかず、間に合う気がしなかった

G

ただのDP

H

数学ゲーorzと思ったけど、入力が2^31と小さかったので、解を全部列挙して埋め込むことにｗ
doubleでn*E-floor(n*E)を計算すると確実に誤差で死ぬなぁと思ったので、BigDecimalを使ったら、遅いのなんの
一時間以上裏で動かし続けてようやく終わった
で、提出したらWAorz
よく考えたらEをMath.Eから持ってきたから有効数字15桁くらいしかなくて、nがでかいと精度が足りないことに気づいたから、BigDecimalでEを計算してもう一回やり直しorz
doubleの精度は15桁くらいだからn*E-floor(n*E)で小数点以下5桁くらいはあるだろうと信じて、まずdoubleで計算してから今までの最小値+1e-4より小さかったらBigDecimalで再計算することにしたら、超速くなって10分くらいで終わった
そしてようやくAccepted
あとから聞いた話だとC++のlongdoubleだと精度が足りたそうだorz
ちなみに卑怯なことしないでどうやって解くんだろうと思って色々試してみたら、Stern-Brocot木でEを小さいほうから近似した時の分母が答えと一致した
証明は知らない

合計8問中6問解いてトップだった様子
やったー