Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

  • A-small/A-Large:Passed, B-small/B-Large:Passed, score:53, penalty(time):1:08:08, rank:319
  • 遅すぎる・・・Round2通過するレベルの目安としては少なくともペナルティは50分以内にしたかった
  • Cが難しかったです

Google Code Jam 2012 Round 1A A Password Problem

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

Problem Statement

解答方針

最初のi個が連続して正しい確率を求めて、何個バックスペースを使うと最も期待値が小さいか調べて、その最小値を返すだけ

なんだけど、色々こまごました式で混乱してしまって20分くらい使ってしまった

終わっとる・・・


ソースコード

入力のパースは省略

double solve(int A, int B, vector <double> &p) {
	double res=0;
	
	vector <double> pn;
	double cp=1;
	for(int i=0; i<A; i++) {
		cp*=p[i];
		pn.push_back(cp);
	}

	res=B+2;
	for(int i=A; i>0; i--) {
		double curk=(A-i)+(B-i+1)+(1-pn[i-1])*(B+1);
		res=min(res, curk);
	}

	return res;
}

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;
}

Google Code Jam 2012 Round 1A C Cruise Control

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

Problem Statement

解答方針

全然解答方針が思い浮かばない、かつBまでで通過した気がしたのでイマイチやる気が出なかった・・・


といいつつ、1時間後くらいに何か二部グラフかどうかの判定をすればいいんじゃないかという気がしたので色々考えてみる

左右のレーンを二部グラフに見立てる

前後5m以内にいる2台を、連結しているノードとみなす

そうすると、このグラフは当然二部グラフでなければならないはずだ

追いつきや抜き去りの発生する全ての時刻で、このような判定をする


何かそれが全てのような気がしてきた

書いた

サンプルの最後が通らない

レーンが固定されているはずの人が、入れ替わったりすることが可能になってしまっている

レーンが固定されているか、入れ替え可能かを判定しつつ二部グラフの判定を行う必要があった


書きなおす

サンプル通った

提出

Wrong Answer


時間切れ

終了


後で

グラフの連結解除をするタイミングが誤っていた

単に抜き去りきっただけで連結を解除してはいけない

その時点で他の人と並走していると、レーンを動かせないので、連結状態が続くとみなさないと状態が崩れる

誰とも並走しなくなった時点で、全ての連結を解除するのが正しい


追いつくタイミングと抜き去るタイミングが混ざっていた

ある時刻tで追いつきと抜き去りの両方が発生する場合、まずは抜き去りだけが完了したとみなして連結の判定をしなければならなかった

追いつきも同時に発生させてしまうと、本来レーン変更が可能なはずなのにできなくなってしまう


他にも細かい間違いがいっぱい

全然だめでした

難しい・・・


ちなみにこの解法は、本質的にはanalysisと同じことをやっています

上位2名の解答を見ましたが、やはり本質的には同様の解法でした

しかし書き方が上手で、うまいこと問題が起きないようにコードが書かれています。短時間ですごい・・・


ソースコード

修正してpractice(Large)に通るバージョン

入力のパースは省略

本体はsolve()です

Possibleのときは1e100を返します

int dfs(int N, int g[52][52], int col[52], int vis[52], int d, int updt) {
	int res=1;
	for(int i=0; i<N; i++) {
		if(g[d][i]) {
			if(col[d]!=2 && col[d]==col[i]) return 0;
			if(vis[i]) continue;
			vis[i]=1;
			int color=col[i];
			if(col[d]==2) assert(col[i]==2);
			if(col[d]!=2) col[i]=1-col[d];
			res&=dfs(N, g, col, vis, i, updt);
			if(!updt) col[i]=color;
		}
	}

	return res;
}

int isbipertite(int N, int g[52][52], int col[52]) {
	int vis[52];
	memset(vis, 0, sizeof(vis));
	for(int i=0; i<N; i++) {
		if(!vis[i]) {
			vis[i]=1;
			int vis2[52];
			int color=col[i];
			int res1=0, res2=0;
			if(color!=1) {
				col[i]=0;
				memcpy(vis2, vis, sizeof(vis2));
				res1=dfs(N, g, col, vis2, i, 0);
			}
			if(color!=0) {
				col[i]=1;
				memcpy(vis2, vis, sizeof(vis2));
				res2=dfs(N, g, col, vis2, i, 0);
			}
			if(!res1 && !res2) return 0;
			else if(res1 && !res2) {
				col[i]=0;
				dfs(N, g, col, vis, i, 1);
			} else if(!res1 && res2) {
				col[i]=1;
				dfs(N, g, col, vis, i, 1);
			} else {
				col[i]=2;
				dfs(N, g, col, vis, i, 1);
			}
		}
	}

	return 1;
}

struct tcmp {
	bool operator()(const vector <int> &a, const vector <int> &b) const {
		if(a[0]*b[1]<b[0]*a[1]) return true;
		if(a[0]*b[1]>b[0]*a[1]) return false;
		return a[2]<b[2];
	}
};

double solve(int N, string C, vector <int> S, vector <int> P) {
	int g[52][52]={0};
	int col[52]={0};
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(i==j) continue;
			if(P[j]<P[i]+5 && P[j]+5>P[i]) {
				g[i][j]=g[j][i]=1;
			}
		}
	}
	for(int i=0; i<N; i++) {
		bool ok=true;
		for(int j=0; j<N; j++) {
			if(g[i][j]) ok=false;
		}
		if(ok) col[i]=2;
		else if(C[i]=='L') col[i]=0;
		else col[i]=1;
	}

	vector <vector <int> > candt;
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(S[i]>=S[j]) continue;
			if(P[i]>=P[j]+5) {
				vector <int> vi;
				vi.push_back(P[i]-P[j]-5);
				vi.push_back(S[j]-S[i]);
				vi.push_back(1);
				vi.push_back(i);
				vi.push_back(j);
				candt.push_back(vi);
			}
			if(P[i]+5>P[j]) {
				vector <int> vi;
				vi.push_back(P[i]+5-P[j]);
				vi.push_back(S[j]-S[i]);
				vi.push_back(0);
				vi.push_back(i);
				vi.push_back(j);
				candt.push_back(vi);
			}
		}
	}

	int gg[52][52]={0};
	sort(candt.begin(), candt.end(), tcmp());
	assert(isbipertite(N, g, col));
	for(int i=0; i<(int)candt.size(); i++) {
		int passtype=candt[i][2];
		int c1=candt[i][3], c2=candt[i][4];
		if(passtype) g[c1][c2]=g[c2][c1]=1;
		else gg[c1][c2]=gg[c2][c1]=1;
		for(int k=0; k<N; k++) {
			bool ok=true;
			for(int j=0; j<N; j++) {
				if(!gg[k][j] && g[k][j]) ok=false;
			}
			if(ok) {
				col[k]=2;
				for(int j=0; j<N; j++) {
					g[k][j]=g[j][k]=0;
				}
			}
		}
		double t=(double)candt[i][0]/candt[i][1];
		if(!isbipertite(N, g, col)) return t;
	}

	return 1e100;
}

ゲスト



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