Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-04-17SRM503 Div1

SRM503 Div1 250 ToastXToast

| 22:58 | SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) SRM503 Div1 250 ToastXToast - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

あまり問題文が分り易くない

ぱっと見、解が最大2にしかならなさそう

よく考えてみても最大2にしかならなさそう

書いた

提出


チャレンジフェーズ

残り5分くらいで明らかにおかしい人を見つけたがおかしすぎて解読しきれず

もっと早く読み解く力を身につけなければ。。。


ソースコード

class ToastXToast {
public:
	int bake(vector <int> un, vector <int> ov) {
		int res=-1;
		sort(un.begin(), un.end());
		sort(ov.begin(), ov.end());
		int n=un.size(), m=ov.size();
		if(un[n-1]<ov[0]) return 1;
		if(un[n-1]<ov[m-1] && un[0]<ov[0]) return 2;
		return res;
	}
};

SRM503 Div1 500 KingdomXCitiesandVillages

| 22:58 | SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) SRM503 Div1 500 KingdomXCitiesandVillages - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何これ近い村から確率1/2していくだけじゃないの?早解きゲームか

書いた→サンプル合わない

常に1/2じゃなかった。手で書き下してみる。

1/2→1/3→1/4→・・・となるみたい。

確認用全探索コードを書く。1/6まで確認した。間違いないぽい

修正。サンプル合った。提出。


手で書き下すところで時間を使い過ぎた。

発想をもっと柔軟にして早く解法を導き出さないと、これ以上の順位が難しいなあ・・・


ソースコード

class KingdomXCitiesandVillages {
public:
	double determineLength(vector <int> cityX, vector <int> cityY, vector <int> vilX, vector <int> vilY) {
		double res=0;
		int n=cityX.size(), m=vilX.size();

		vector <double> distv[52];
		for(int i=0; i<m; i++) {
			double mind=1e100;
			for(int j=0; j<n; j++) {
				double d=hypot(vilX[i]-cityX[j], vilY[i]-cityY[j]);
				mind=min(mind, d);
			}
			for(int j=0; j<m; j++) {
				if(i==j) continue;
				double d=hypot(vilX[i]-vilX[j], vilY[i]-vilY[j]);
				if(d<mind) distv[i].push_back(d);
			}
			sort(distv[i].begin(), distv[i].end());
			double p=1;
			for(int j=0; j<(int)distv[i].size(); j++) {
				res+=distv[i][j]*p/(j+2);
				p=p*(j+1)/(j+2);
			}
			res+=mind*p;
		}

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