504.5.1

SRM504がうまくいかなかったのはlimitのせいじゃなかったよ、という主張なのだろうか？

250

末尾が4または7の数字を足し合わせて、整数Nを作るとき、最小で何個足し算すれば良いか、という問題。

取り敢えず10個以上使う必要はなさそうなので、それぞれ10個以下のものを全探索するだけ、ということに気付くのに凄い時間かかった...。

550

N人でKのお金を分ける。まず全員の所持金の平均値を求め、一番所持金の少ない人が平均値を上回るようにお金を渡す。これを繰り返す。足りないときは残り全部渡す。最終的な所持金を答えよ、という問題。

取り敢えず、全員の所持金の差分が小さくなる方向に進むので、分け方が1ずつの増加になったら、N人で均等配分、というような処理を追加しておく必要がある。後は愚直にやるだけ。差分が大きい時はおよそ1/Nだけ差分が埋まっていくので比較的すぐに収束する。値が大きいのでlong溢れに注意する必要がある。

900

N人の列のM番目にいる。先頭の人がサイコロを振って、1が出れば勝ち。2か3なら失格で、それ以外は列の後ろに並び直す。このとき、勝つ確率を求めよ、という問題。

取り敢えずN-1人の列のときに、各位置の人の勝率が分かっているとする。また、N人の列で一つ前の人が勝つ確率が分かっているとする。このとき、前の人が後ろに回れば、前の人の勝つ確率で勝てるし、失格になればN-1人の列のときの確率で勝てる。それ以外は前の人が勝ってるので勝てない。なので先頭の人が勝つ確率だけ求めてやる必要がある。先頭の人が勝つ確率をXとすると、一周して戻ってくる確率がPだとして、一周する間に勝っている確率がYなら、X=Y+P*Xになるので、これを解けばおしまい。(Nが大きいとPはほぼ0になるような気もする。)

TopCoderの確率の問題は大抵DPでできるっぽい。