TopCoder SRM 568 Div2 Hard ShuffleSort

さてDiv2 Hard。
本番終了後、「Div2 HardよりDiv2 Medium(Div1 Easy)の方が簡単！」って騒いでる人がいたけど、確かに今回Div2とはいえHardの割に優しかった。
http://community.topcoder.com/stat?c=problem_statement&pm=11156

カードをランダムにシャッフルし、先頭に最小値が来ていたらそのカードを取り除く。
取り除いた残りの最小値が残りの先頭なら、それも取り除く。
全カードを取り除くまでにシャッフルする回数の期待値を求める。
なお、最初からカードが小さい順に並んでいても、初回１回はシャッフルする。

まず与えられたカード群をソートしてしまおう。
また、最初のシャッフル１回は無条件にカウントする。

数字の小さい順に見ていくと、シャッフルでその数字が先頭にくる確率は(同じ数字のカードの枚数)/(残カード数)であり、先頭にくるまでのシャッフル回数の期待値をその逆数である。
また、初回は前回のシャッフルで１つ前のカードを取り除いてそのまま次の先頭カードの数値判定に入るので、各カード初回はシャッフルの必要が無いので1回減らす。

残ったカードの数値が全部同じならそれ以上シャッフルの必要はないので終了。

下記のコードは再帰で書いたけど、メモ化もしてないし１方向だし簡単なループで書いても良かったね。

class ShuffleSort {
	int N;
	vector<int> C;
	public:
	double val(int left) {
		if(C[left]==C[N-1]) return 0;
		
		int i;
		int num=0;
		for(i=left;i<=N-1;i++) if(C[left]==C[i]) num++;
		
		return (N-left)/(double)num - 1 + val(left+1);
	}
	
	double shuffle(vector <int> cards) {
		N=cards.size();
		sort(cards.begin(),cards.end());
		
		C=cards;
		return 1+val(0);
	}
};

まとめ

この問題、初回でいきなりサンプルケースも通って本番も通ったのでびっくり。
もうちょい数値の手直しで手間取るかと思ったのに。
Hardにしてはコード量も少ないね。

内容としてはGCJ2011 QRのGorosortを思い出した。