Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-06Google Code Jam 2012 Round 1A

Google Code Jam 2012 Round 1A B Kingdom Rush

| 20:30 | Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

なぜか1-starクリアの数で二分探索なんじゃないかと思ってしまった

いやいや、そもそも上限1000で二分探索なんか普通いらんし・・・

というか何で二分探索なんだ。どの面を1-starに選ぶか決められないとそんな手法取れないし

逆にそれが決められるなら二分探索いらない気がする


もう一度落ち着いて考える

ある状態で2-starに行ける面があるなら、常に取ってしまっていい

ある状態で1-starしか行けないとき、どの面を選ぶかが問題になる

1-starの必要star数を満たしていないものは当然除外する

1-starの必要star数を満たすものの中で、2-starの必要star数が小さいものを残しておいたほうが、総合的に1-starクリア数を減らせるんじゃないか

これで行けば、Greedyでいいことになる


問題文中のサンプルの進め方と異なるが、本当に正しいか。

(1-starの必要star数,2-starの必要star数)という表現で具体的な例を考える

(0,1)と(0,3)があったとする

  • (0,1)からクリアすると、(0,1),(0,1),(0,3),(0,3)の順で合計4回クリアする必要がある
  • (0,3)からクリアすると、(0,3),(0,1),(0,3)の順で合計3回クリアでいける

どちらの1-starを取っても、2-starの必要star数は変わらないし、もらえるstar数も変わらない

だったら、なるべく早い時点で2-starが取れる可能性のある方を残しておいたほうが得に決まっている

やはり正しそうだな

サンプルはたまたまどちらから進めても同じ結果になる例なだけっぽい


とりあえずできたが無駄に時間がかかった。最悪・・・


ソースコード

入力のパースは省略

Too BadのときはN*2+1を返します

int solve(int N, vector <int> &a, vector <int> &b) {
	int res;
	
	int star=0;
	vector <int> done1(N), done2(N);
	for(int one=0; one<=N; one++) {
		bool cont=true;
		while(cont) {
			cont=false;
			for(int i=0; i<N; i++) {
				if(done2[i]) continue;
				if(star<b[i]) continue;
				done2[i]=1;
				if(done1[i]) star++;
				else star+=2;
				cont=true;
			}
		}
		int maxb=-1, maxbi=-1;
		for(int i=0; i<N; i++) {
			if(done1[i] || done2[i]) continue;
			if(a[i]<=star && b[i]>maxb) {
				maxbi=i;
				maxb=b[i];
			}
		}
		if(maxb==-1) break;
		done1[maxbi]=1;
		star++;
	}

	res=N;
	for(int i=0; i<N; i++) {
		if(!done2[i]) return N*2+1;
		res+=done1[i];
	}

	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120506