TopCoder SRM422

TopCoderのことでも書けばアクセス増えるかねえ。
そんなんで増えてもどうしようもない気がするが・・・。

さてICPC練習会なんかで最近のサボりが浮き彫りってレベルじゃねーぞ状態の中一軍戦に突撃。
過去に一瞬一軍に上がって一問も解けず即死したことがあるので怖すぎて困る。

• Easy

AチームとBチームが1ターンごとに1点を入れる確率が与えられる。試合時間は18ターン。最終得点がどちらか一方でも素数となる確率を求めよ。
数学Aで見たような二項定理な確率。
n回やってr回確率pの事象が起こるのは
nCr p^r (1-p)^(n-r)
今回はn=18で固定、rはちょうど得点数になります。
r=2,3,5,7,9,11,13,17
で和をとりましょう。
最後は足して両方とも素数の確率を引く
とかなんとかでちょこちょこっと。
pa + pb - pa*pb

• Medium

重さ、渡る速さの異なる13人以下のメンバーが一定の重さまでしか耐えられない橋を全員が渡る。
また、各個人に信頼フラグがあり、同時にわたる場合メンバーに少なくとも１人は信頼しているメンバーがいなくてはならない(すべての２人についてお互いに信頼しているとは限らない)。
橋を渡るとき、誰か１人が地図を持っていなければならない。
同時にわたる場合、最も遅い人に全員が合わせなければならない。
どっからどうみてもgoogleかなんかの入社試験かなんかです。
ひっかけポイントがそこらじゅうに張り巡らされている気がして私はひるんでしまった。
ビットDPで貪欲ゼロでいける(というか貪欲1点でも使った時点で死ぬだろうな)とわかってもすでに戦意消失しているのだった・・・。

1370->1355
ぬああああ
ほんの少し下がったあああ
しかし毎回これほどのレベルが出るMediumを当てにするわけにはいかないしどこからどうみても近道はEasy高速化です。
コンビネーションの計算でオーバーフロー恐れてdoubleで掛け算と割り算を交互にやって0.4を足して切り捨てるという超チキンプレイ。
しかしミスると多分２軍直行なのが怖いところ。
落ちないところで少しずつ速くして慣れるのを待つか・・・。

Google Code JamでRound3までいったのは何だったんですか。
ほんと今どうあるかが大事ですよ。