Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

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