Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-04-25SRM541 Div1

SRM541 Div1 250 AntsMeet

| 01:12 | SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) SRM541 Div1 250 AntsMeet - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

任意の蟻のペアで衝突判定をして、時間の早い順に並べて、死んだ蟻を取り除きながら真の衝突判定をする

とか思ったけどあまりにも面倒そうだったので他の手段を検討

単純なシミュレーションで間に合うことに気づいたので書く

サンプル合った

提出


チャレンジフェーズ

ボロボロと周りが落とされていくんだが全然何が悪いのか分からない

どうやら座標を2倍していない人がたくさんいたらしい

サンプルにそういう例があるのでまさか2倍せずに(or 0.5刻みにせずに)提出してる人がいるとは思っていなかった・・・


ソースコード

class AntsMeet {
public:
	int countAnts(vector <int> x, vector <int> y, string dir) {
		int res;
		int n=x.size();

		for(int i=0; i<n; i++) {
			x[i]*=2;
			y[i]*=2;
		}

		int dis[52]={0};
		for(int t=0; t<10000; t++) {
			for(int i=0; i<n; i++) {
				if(dir[i]=='N') y[i]++;
				if(dir[i]=='E') x[i]++;
				if(dir[i]=='S') y[i]--;
				if(dir[i]=='W') x[i]--;
			}
			for(int i=0; i<n; i++) {
				if(dis[i]) continue;
				for(int j=i+1; j<n; j++) {
					if(dis[j]) continue;
					if(x[i]==x[j] && y[i]==y[j]) {
						dis[i]=dis[j]=1;
					}
				}
			}
		}

		res=0;
		for(int i=0; i<n; i++) if(!dis[i]) res++;
		
		return res;
	}
};

PraveenPraveen2012/11/14 15:22You've really captured all the esstenials in this subject area, haven't you?

lltwektgdjilltwektgdji2012/11/17 00:38s3e55e <a href="http://weadgecnprbz.com/">weadgecnprbz</a>

zkwvhwizkwvhwi2012/11/17 10:47mzuI7w , [url=http://amjymbwsqtpw.com/]amjymbwsqtpw[/url], [link=http://jtoocgzxmaus.com/]jtoocgzxmaus[/link], http://uoyfejtwsvcz.com/

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