Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-01Google Code Jam Japan 2011 予選

Google Code Jam Japan 2011 予選 A カードシャッフル

| 20:14 | Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーション

正順でやるとLargeで時間に間に合わないため、逆順でシミュレーションする

こういう逆からなら計算量が削減できるというのは慣れていないと分かりにくい気もする

提出時間:Large 14m46s


ソースコード

int solve(int M, int C, int W, vector <int> &A, vector <int> &B) {
	int res=0;
	W--;
	for(int i=0; i<C; i++) {
		A[i]--;
	}
	
	for(int i=C-1; i>=0; i--) {
		if(W<B[i]) {
			W+=A[i];
		} else if(W-B[i]<A[i]) {
			W-=B[i];
		}
	}

	res=W+1;
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int M, C, W;
		ifs >> M >> C >> W;
		vector <int> A(C), B(C);
		for(int i=0; i<C; i++) {
			ifs >> A[i] >> B[i];
		}
		int res=solve(M, C, W, A, B);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111001