SRM568 Div2 Hard(1000) ShuffleSort

ShuffleSort

数字が最小のカードがa枚、それ以外のカードがb枚ある場合に、カードを1枚減らすのに必要なシャッフルの期待回数をcとすると、c=1+cb/(a+b)。よって、c=(a+b)/a。step 2を何回も繰り返すルールは、カードが減ったときにはstep 1を省略できると考えると、最後にn-1を引けば良いことが分かる。

#include <vector>
#include <algorithm>
using namespace std;

class ShuffleSort{public:
double shuffle( vector <int> cards )
{
    int n = (int)cards.size();
    sort(cards.begin(),cards.end());

    double ans = 0;
    for ( int i=0; i<n; i++ )
    {
        int a = 0;
        for ( int j=i; j<n; j++ )
            if ( cards[j]==cards[i] )
                a++;
        ans += double(n-i)/a;
    }

    return ans-(n-1);
}};