Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-05Google Code Jam 2011 Round 2

Google Code Jam 2011 Round 2 A Airport Walkways

| 21:25 | Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

歩く速さと走る速さの差は一定なので、歩道が遅いときに走るほど効果が高い

例:歩く速さ2、走る速さ4、歩道Aの速さ2、歩道Bの速さ4とすると、Aで走ると歩きの1.5倍の速さ、Bで走ると歩きの1.333倍の速さになるので、Aで走ったほうが得

ということで、歩道の速さでソートして遅い歩道からGreedyに走るようにすればOK

すぐ解けた

提出時間:Large 18m28s


ソースコード

入出力は省略。

tはdoubleに変換してある。

double solve(int X, int S, int R, double t, int N, vector <int> B, vector <int> E, vector <int> w) {
	double res=0;

	vector <pair <int, int> > wl;
	int nw=X;
	for(int i=0; i<N; i++) {
		wl.push_back(make_pair(w[i], E[i]-B[i]));
		nw-=E[i]-B[i];
	}

	wl.push_back(make_pair(0, nw));
	sort(wl.begin(), wl.end());

	for(int i=0; i<(int)wl.size(); i++) {
		double tt=(double)wl[i].second/(R+wl[i].first);
		if(tt>t) {
			double len=(R+wl[i].first)*t;
			tt=t+(double)(wl[i].second-len)/(S+wl[i].first);
			t=0;
		} else t-=tt;
		res+=tt;
	}
	
	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110605