A: Irrational problem
方針
やるだけ
実装
Codeforces は Ruby で書くのが常だが、next_permutation が使いたかったので C++ で書いた。
next_permutation するときは、事前のソートを忘れずに!
B: Energy exchange
方針
一台あたり エネルギー E にできるなら、任意の e < E にすることもできる。なぜなら、余ったエネルギーは、二台のあいだでお手玉させて消せるから。したがって、二分探索可能
実装
Codeforces #60 C: "Harry Potter and the Golden Snitch" の教訓を活かして実装。ループ回数は固定。出力はOKな側を(実は、逆を出してた……。通ったからいいけど、危ない危ない)。浮動小数点の出力前には、setprecisionする。
C: Synchrophasotron
方針
いろいろ考えたが分からない
D: Half-decay tree
方針
問題のサイズ的に、全部試すのは無理だろう。となると、数学ガール4巻でも強調されていた、期待値の線形性を使うことになりそう。深さ3くらいを手で試してみると、各ノードは(根を除いて) 1/2 の確率で寄与することになる。ということは、各ノードの値に 1/2 をかけて足すだけ? しかも、ノードをバラバラに考える必要はなくて、深さごとに電子数を覚えておけばよい。
書く。テストケース通る。え? と思いつつ提出。― pretest 2 で落ちる。あ、『「一番大きな component」の値』じゃなくて、『「一番大きな値になるcomponent」について、その値」の期待値だった。だめじゃん。世の中甘くなかった。
A を見る
やることなくなったので、A を Lock して他の人のを見る。1時間以上かかって出した黒色の人で、p を sort してるけど、next_permutation してない解答を発見。しめしめと思いながら、撃墜を狙う。一応、自分のコードを next_permutation しないようにして、答えが食い違うケースを探す。……あれ? 落ちない。もしかして、mod p[i] する順序って可換!?
結果・感想
A, B 通る。下がるかと思ったが、1752→1758 と微増。
もう一問解きたいなぁ。とはいえ、B の二分探索を解けたのは嬉しい。
