SRM 568 div2 hard: ShuffleSort
解法
問題見てすぐに dp[n] = (残り n 枚の時, card をソートし終えるのにかかる回数の期待値) というのが思いつきますが, 素直に遷移を書くと面倒なので, もう少し考えます。
n 枚のカードが残っている際に, 最小のカードは t 枚残っているとすると, 最小のカードを引かない確率は 1-t/n で, 他の場合は最小のカードを引きます。最小のカードを引いた場合, 1 回シャッフルするという手間を省いて次の最小のカードがどうなっているかを調べる, と考えても同じであるので,
dp[n] = (1-t/n) * (1+dp[n]) + t/n * (1+dp[n-1]-1)
という漸化式が成り立ちます。これを簡単化して,
dp[n] = n/t - 1 + dp[n-1]
という漸化式を更新していけば良いです。
double dp[55]; class ShuffleSort { public: double shuffle(vector <int> cards) { sort(cards.rbegin(), cards.rend()); dp[1] = 1; int n = cards.size(), t = 1; for (int i = 2; i <= n; i++) { if (cards[i-1] == cards[i-2]) t++; else t = 1; dp[i] = (1.*i/t-1) + dp[i-1]; } return dp[n]; } };