Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-08Google Code Jam 2011 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;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110508