SRM568 Div2 Hard(1000) 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); }};