hotpepsiの練習帳

SRM 656

02:07

https://competitiveprogramming.info/topcoder/srm/round/16416/div/1

Div1 Easy (250)

問題

• N枚のパンケーキがある
• それぞれの大きさは1からNで、それぞれのおいしさが与えられる
• 1枚ずつランダムに選んで積んでいく
• ただし、一つ前に積んだものより大きければ、それを積まないで終了
• 詰まれたパンケーキのおいしさの合計の期待値を求める

方針

• 座るだけ
• (終了後)
• こじはらさんのブログを参考に
• 全体の並べ方はN!通り
• 並べ替えの結果、i番目(0-index)のパンケーキがj番目(0-index)にあるとき、それがおいしさにカウントされる(終了していないとき)は、前半がカウント条件を満たしていたときで、その総数は、i番目より大きなg個(N-i-1個)のパンケーキからj個取った場合の数。g!÷((g-j)!×j!)通り。
• 後半についてはカウント条件に関わらず全て数える(後半の並びかた関わらず、i番目のパンケーキのおいしさをカウントするかどうかだけ気にすればよい)
• 後半のr個(N-j-1個)の並べ方はr!通り
• すなわちi番目のパンケーキのおいしさの総和はg!÷((g-j)!×j!)×r!×おいしさ
• 期待値は全体の並べ方はN!なので最後にそれで割る
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_656/RandomPancakeStack.cpp

結果

--- -1 -25pt 517th/531 rating 1543 -> 1384 (-159)

考察不足。

http://togetter.com/li/809565