TopCoder SRM 656 Div.2 Med: RandomPancakeStackDiv2
手間取ったがきれいに書き下せたので満足。
問題はこちら。
問題
パンケーキがN枚あり、それぞれに0からN-1の番号が振られている。i番目のパンケーキは幅i+1でおいしさがd[i]である。このパンケーキを次の手順で皿のうえに重ねていく。
- 皿に乗ってないパンケーキがないなら、手順を終える
- 残っているパンケーキからランダムに1枚選ぶ
- 選んだパンケーキの幅が皿に乗っている一番上のパンケーキよりも小さければ上に重ねる。そうでなければ手順を終える。
- 1に戻る
1番最初に選んだパンケーキは必ず皿に乗せられるとする。手順を終えたときに、皿の上に重なったいるパンケーキのおいしさの合計の期待値を答えよ。
解法
再帰で解ける。残っているパンケーキの枚数と一番上のパンケーキの幅を持っておけばよい。一番最初に選ぶパンケーキを決めた後は、その幅より小さなパンケーキを選んで再帰的に計算していけばいい。
def dfs(n, m, d): res = d[m] for i in xrange(m): res += 1.0/n*dfs(n-1, i, d) return res def expectedDeliciousness(self, d): N = len(d) ans = 0 for i in xrange(N): ans += 1.0/N*dfs(N-1, i, d) return ans
まとめ
Div1Easyの場合はmemo[n][m]というふうなメモ化を施してやれば通すことができる。