TopCoder SRM466

ひさびさの参戦。わりと自分の得意な感じのセットでした。

250

（問題）略。


（解法）約数が奇数個　⇔　平方数なの。


→　209.65　→　Passed

500

（問題）1<=N<=100
N行5列のマス目に、1〜5Nまでの自然数を1つずつランダムに埋めます。
また、「当たり番号」を、1〜5Nの中から5つ、ランダムに決めます。
当たり番号が3つ以上含まれている行が存在したら、当たりです。当たる確率を求めなさい。


（解法）
当たり番号は1,2,3,4,5だと仮定してよい。
マス目の埋め方は、全部で(5N)P(5)通り。
「当たり番号がちょうど3つ含まれている行がある」場合の数をPとかCとか使って計算。（5C3*n*5P3*(5N-5)P2）
「当たり番号がちょうど4つ含まれている行がある」場合の数をPとかCとか使って計算。（5C4*n*5P4*(5N-5)P1）
「当たり番号がちょうど5つ含まれている行がある」場合の数をPとかCとか使って計算。（5C5*n*5P5*(5N-5)P0）
全部足す。


（感想）
・入力によって計算量が変わらない500とは珍しい。
・nCrライブラリとかnPrライブラリとかあると地味に便利。
・てかこれ400で良かったんじゃね？


→　387.28　→　Passed

1000

（問題）略。


（解法）dp[20][2^8]を使ってメモ再帰でdp。
最初から置いてあるBをボムと表現し、Blackで上書きされるものと考える。
dp[i][j]には、iターン目、jで表されるボムが残っている状況からゲームを始めたときの場合の数を入れる。
O(20*(2^8)*400)。ちょっと工夫すればもちっと速くなりそうだけどまあいいや。


↑を実装してコンパイルまでは行ったけど、バグが取れず。


（追記）後日、2つほど小さいバグを取ったらちゃんと通った。いたくやしい。
てかこれ900で良かったんじゃね？
（そう思えることが、今回のが得意セットだったという証）

結果

1撃墜して、646.93点。69位。R：1730　→　1865。
赤遠い。