roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 656 Div.2 Med: RandomPancakeStackDiv2

手間取ったがきれいに書き下せたので満足。

問題はこちら

問題

パンケーキがN枚あり、それぞれに0からN-1の番号が振られている。i番目のパンケーキは幅i+1でおいしさがd[i]である。このパンケーキを次の手順で皿のうえに重ねていく。

  1. 皿に乗ってないパンケーキがないなら、手順を終える
  2. 残っているパンケーキからランダムに1枚選ぶ
  3. 選んだパンケーキの幅が皿に乗っている一番上のパンケーキよりも小さければ上に重ねる。そうでなければ手順を終える。
  4. 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]というふうなメモ化を施してやれば通すことができる。