SRM338

テスト期間中だけど(ry

250pt

229.20. オーバーフロー注意。

500pt

339.27. 後述。

1000pt

Compiled. よくわかってない。lexicographically smallestとか嫌がらせ以外の何者でもないですよね。

レーティングは1982->2026。解法の難易度の割に500pt.の提出が遅くなってしまったのだけど、特に後悔はない。今回は堅実に行けたんじゃないかな。次回もこんな感じで。

以下、500pt.についての話を少し。500pt.を早く解いた人には是非教えてほしいことが。

500pt.は確率の線形漸化式が導出できて、与えられた回数分だけそれ繰り返せば答えが出るということは分かる。問題は誤差。

出力は絶対誤差・相対誤差のいずれかで1.0e-9以下で無ければいけないんだけど、漸化式では有効数字20bit程度の小数を10^5回ほど掛けたり足したりすることになる。これって本当に大丈夫なのかいな、ということでイタレーションを無くして標準ライブラリのべき乗関数が使える形に持っていった上で*1long doubleを使って... とやってこんなコードになったのだが、結局はイタレーションだけでいいらしい。そりゃそれだけでいいなら400点台中ほどで提出できるよなあ…

swapをしていくほど注目しているカードの存在確率は一様になっていくので、確率はswap回数に関して単調に増加/減少する。確率の収束速度が速くて誤差が表れにくいのかな？ よく分からない…

単純な反復で書いてささっと提出した人が、どう考えてその方法で大丈夫だと確信できたのか知りたいなあ。

*1:ライブラリの数学関数はあの手この手を使って最大限の精度を出せるように工夫されているので、自分で書くより圧倒的に正確かつ速い。