SRM 568 div2 hard: ShuffleSort

問題

TopCoder Statistics - Problem Statement

解法

問題見てすぐに 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];
    }
};