TopCoder SRM526.5

250

なにかがN個あり、1〜Nの番号がついている。「平方数番目のものをすべて取り除き、元の番号順に1から順に番号を付け直す」行為を1個になるまで行う。最後に残ったものは最初何番目だったか。

よくわからないので再帰を使って解いたらNが1,000,000,000のとき最初TLEだったがsqrtの計算をO(1)にしたら1.2秒だったので安心して送った

500

広い平面上に雪玉が降る。それぞれの雪玉はグリッド上のある範囲に等確率で落ちる。「-R <= x,y <= Rの範囲に雪玉がc個降る」という情報がN個与えられる。すべて降り終わった時のグリッドの美しさの期待値を求めよ。美しさは、各マスについて、「(そのマスに降った雪玉の数)^2」を計算し、その総和である。

グリッドは降る可能性のある雪玉の種類によって高々N通りに分けられる。各マスについて、すべての雪玉の降る確率を計算しておく。
そのマスについての美しさの期待値は、Σj^2・(そのマスにj個の雪玉が降る確率)である。これは、Σp、Σj・p、Σj^2・pを順次計算することで計算できる。

1000

不明

結果

oox 239.24 + 285.41 + 0.0 = 524.65 17位
2044 -> 2184