Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-08Google Code Jam 2011 Qual Round

  • Qual Roundだけあって難しい問題はない

Google Code Jam 2011 Qual Round A Bot Trust

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

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

入出力処理は省略

Rは色、Pはボタン位置を示す

int solve(int N, string R, vector <int> P) {
	int res=0;
	
	int o=1, b=1;
	vector <int> O, B;
	for(int i=0; i<N; i++) {
		if(R[i]=='O') O.push_back(P[i]);
		else B.push_back(P[i]);
	}

	int oi=0, bi=0, i=0;
	while(i<N) {
		res++;
		bool odone=true, bdone=true;
		if(oi<(int)O.size()) {
			if(O[oi]>o) o++;
			else if(O[oi]<o) o--;
			else odone=false;
		}
		if(bi<(int)B.size()) {
			if(B[bi]>b) b++;
			else if(B[bi]<b) b--;
			else bdone=false;
		}
		if(!odone && R[i]=='O' && O[oi]==o) {
			i++; oi++;
		} else if(!bdone && R[i]=='B' && B[bi]==b) {
			i++; bi++;
		}
	}

	return res;
}

Google Code Jam 2011 Qual Round B Magicka

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

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

入出力処理は省略

combはcombine、oposはopposed(oppoにすれば良かった?)、invoはinvokeをそれぞれ示す

string solve(int C, int D, int N, vector <string> comb, vector <string> opos, string invo) {
	string res;
	
	int appear[256];
	memset(appear, 0, sizeof(appear));
	char prev=127;

	for(int i=0; i<N; i++) {
		res.push_back(invo[i]);
		appear[invo[i]]++;
		for(int j=0; j<C; j++) {
			if(prev==comb[j][0] && invo[i]==comb[j][1] || prev==comb[j][1] && invo[i]==comb[j][0]) {
				res.erase(res.size()-2, 2);
				res.push_back(comb[j][2]);
				appear[prev]--;
				appear[invo[i]]--;
				appear[comb[j][2]]++;
				prev=comb[j][2];
				break;
			}
		}
		for(int j=0; j<D; j++) {
			if(appear[opos[j][0]] && appear[opos[j][1]]) {
				res.clear();
				memset(appear, 0, sizeof(appear));
				prev=127;
				break;
			}
		}
		if(res.empty()) prev=127;
		else prev=res[res.size()-1];
	}

	return res;
}

Google Code Jam 2011 Qual Round C Candy Splitting

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

Problem Statement

解答方針

パトリックの計算方法はxorに等しい

ある2つの集合に分けたとき、各集合のxorがx1、x2となるとすると、xorの性質よりx1=x2のときx1^x2=0

従ってNOとなる条件は、全てのキャンディをxorして0にならないこと

また、NOとならない場合x1^x2=0となることから、どのような分け方をしてもx1=x2となる

なのでパトリックには一番価値の低いキャンディを1つあげれば良い


ソースコード

入出力処理は省略

NOの場合は-1を返す

int solve(int N, vector <int> C) {
	int res=0;
	
	int cur=0;
	for(int i=0; i<N; i++) cur^=C[i];
	if(cur!=0) return -1;

	sort(C.begin(), C.end(), greater <int>());
	res=accumulate(C.begin(), C.end()-1, 0);
	return res;
}

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