Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-21SRM538 Div1

SRM538 Div1 250 EvenRoute

| 20:26 | SRM538 Div1 250 EvenRoute - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM538 Div1 250 EvenRoute - SRM diary(Sigmar) SRM538 Div1 250 EvenRoute - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

チェッカーボードで同じ色の間を移動するのなら、どんな経路を通っても偶数ステップになるんじゃないか

逆に違う色の間を移動するのなら、どんな経路を通っても奇数ステップになるんじゃないか

正しいっぽい

ということは原点と最後に訪れる点だけ決めればパリティが決まるし、どんな経路を通ってもいいのだから全ての点を通ってきたとすればいい

各点の原点からのマンハッタン距離のパリティを調べれば終わり

久々に結構すぐ解けた


ソースコード

class EvenRoute {
public:
	string isItPossible(vector <int> x, vector <int> y, int wp) {
		string res;
		int n=x.size();

		int par1=0, par0=0;
		for(int i=0; i<n; i++) {
			if((x[i]+y[i])%2==0) par0=1;
			else par1=1;
		}

		if(par0 && par1) return "CAN";
		if(wp==1 && !par1) return "CANNOT";
		if(wp==0 && !par0) return "CANNOT";
		return "CAN";
	}
};

SRM538 Div1 450 TurtleSpy

| 20:26 | SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) SRM538 Div1 450 TurtleSpy - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

直感的には、forwardとbackwardは全部結合して、forwardとbackwardの間に最適な角度を差し込めばいいように思われる

本当かな・・まあ450だし書いてみよう

適当なDPを書く

意外と時間がかかってしまった・・・実装力低すぎる・・・

とりあえずサンプル通ったんで提出

しかしアルゴリズム的に楽勝すぎる。本当に大丈夫か。これじゃあ450っていうより300くらいのような・・

forwardしてbackwardしてまたforwardするのがいいようなパターンはないのか

  • 一回目のforwardのベクトルとbackwardのベクトルを足すと、新たなベクトルができる。
  • 二回目のforwardのベクトルの方向が、一回目のforwardのベクトルと新たなベクトルの間に入るようにできれば、forwardを分割したほうがいい
  • どうやら検討してみると、そのような二回目のforwardを作れる回転があるなら、backwardする前に使ったほうがいい結果になるっぽい

なんだ。つまらない。しかし解くよりも証明するほうが大変そうな気がする。チキンレース気味だな。


ソースコード

ベクトルの回転にはpolarという便利な関数を使用する

まあ別に使わなくても大した差はないが・・・


あと、leftとrightを分けた辺りがちょっと無駄だった。rightはマイナスの値にしとけば良かったかな・・・

typedef complex <double> pt;

int la[52][370], ra[52][370];

class TurtleSpy {
public:
	double maxDistance(vector <string> com) {
		double res;
		int n=com.size();

		vector <int> l, r;
		int f=0, b=0;
		for(int i=0; i<n; i++) {
			stringstream ss(com[i]);
			string s;
			ss >> s;
			int v;
			ss >> v;
			if(s=="forward") f+=v;
			if(s=="backward") b+=v;
			if(s=="left") l.push_back(v);
			if(s=="right") r.push_back(v);
		}

		memset(la, 0, sizeof(la));
		memset(ra, 0, sizeof(ra));
		int lsz=l.size(), rsz=r.size();

		la[0][0]=ra[0][0]=1;
		for(int i=0; i<lsz; i++) {
			for(int a=0; a<360; a++) {
				if(!la[i][a]) continue;
				la[i+1][a]=1;
				int na=(a+l[i])%360;
				la[i+1][na]=1;
			}
		}
		for(int i=0; i<rsz; i++) {
			for(int a=0; a<360; a++) {
				if(!ra[i][a]) continue;
				ra[i+1][a]=1;
				int na=(a+r[i])%360;
				ra[i+1][na]=1;
			}
		}

		int aa[360];
		memset(aa, 0, sizeof(aa));
		for(int i=0; i<360; i++) {
			for(int j=0; j<360; j++) {
				if(la[lsz][i]&&ra[rsz][j]) aa[((i-j)+360)%360]=1;
			}
		}

		int besta=0;
		for(int i=0; i<360; i++) {
			if(aa[i]) {
				if(abs(180-i)<abs(180-besta)) besta=i;
			}
		}

		pt p(f, 0);
		pt ap=polar((double)b, M_PI*((besta+180)%360)/180.);
		p=p+ap;
		res=abs(p);
		
		return res;
	}
};

EsmeEsme2012/11/15 09:54Fell out of bed feeling down. This has brihgtened my day!

dfcfxtaudfcfxtau2012/11/17 05:21FAXLCr , [url=http://nigkynubluqk.com/]nigkynubluqk[/url], [link=http://sdzcawuwyqac.com/]sdzcawuwyqac[/link], http://eralavivvuvl.com/

fsakkadkfsakkadk2012/11/17 21:48Ln0gXw , [url=http://vgjurqseohhr.com/]vgjurqseohhr[/url], [link=http://gcpmrqxsqmmm.com/]gcpmrqxsqmmm[/link], http://mlzyuaxtrdqy.com/

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