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";
	}
};

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