Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-08Google Code Jam 2011 Qual Round

Google Code Jam 2011 Qual Round D GoroSort

| 13:14 | Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルを見ると、1,2と3,4でそれぞれ入れ替わっていてグループ化できる

何となく位置が入れ替わっているものをグループ化してそれぞれ入れ替えてやれば良さそうである

その場合、各要素が正しい位置に行く可能性はそれぞれ要素数分の1であるため、大体一回のシャッフルで1個の位置が合うものと想定できる

従って、グループ化したときの要素数がおそらくシャッフル回数の期待値である(ただし要素数1のときを除く)

以上から、グループ化して要素数1個以外の要素数を全て足しあわせたものが解となる


と考えて解答したがAnalysisを見たところ、グループ化しなくても良く、正しい位置にない要素の数が解となるとのこと。

確かに自分の解答と答えは同じになるが、グループ化してシャッフルしなくても良いというのは少し直感的ではなかったのでなかなか面白い。


ソースコード

入出力処理は省略

以下はグループ化した書き方になっています

(Pの要素は元々1baseになっていたので0baseとなるよう全て-1してある)

double solve(int N, vector <int> P) {
	double res=0;
	
	vector <int> used(N);
	for(int i=0; i<N; i++) {
		if(used[i]) continue;
		int cur=P[i];
		int cnt=0;
		while(!used[cur]) {
			used[cur]=1;
			cur=P[cur];
			cnt++;
		}
		if(cnt>1) res+=cnt;
	}
	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110508