SRM513

解答例

250

全探索。

500

「揃うことが確定しているペアがあるならそれをめくる、そうでないなら未知のカードをめくる」が最善戦略。
dp[i][j]＝「場にi枚残っていてそのうちj枚が1度はめくられたことのあるカードである状態から始めて、最善戦略をとったときにかかるゲーム終了までに必要なターン数の期待値」とでもおいてDP。O(2500^2)。

参加記

250　→　175.41

10000*50*50を計算したら2億5000万になったので若干面倒くさいことをした。
途中まで問題文読み間違えて答えが合わなかった。

500　→　220.24

double dp[2500][2500]のサイズを計算したら500MBになったので若干面倒くさいことをした。
途中まで漸化式間違えてて答えが合わなかった。
若干面倒くさいことをしたせいでバグって再提出。

結果

R2188 → R2189
どうしようもない。