Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-01SRM474 Div1

SRM474 Div1 250 RouteIntersection

| 23:55 | SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) SRM474 Div1 250 RouteIntersection - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→うーん・・・座標をvectorで保存してシミュレーションするだけではないのか、これは・・

→通った点の座標をsetに入れて、移動した数+1より小さければNOT VALIDかな

→書いてみる

→あ、、だめだ、よく見たら次元の最大は10億なのでvectorで表せない

→といっても50個しか点が出てこないので、とりあえず出現する次元にmapで適当にIDをつけてしまおう

→書く→サンプル通る

→mapを使うところ以外は難しいところはない。少し簡単すぎるので不安。。引数Nを使わないというのも大丈夫か、これ・・

→5分ほどかけてコーナーケースなどをチェック

→問題ない。提出

→500へ


チャレンジフェーズ

→10億個vectorを確保しようとしてる人はいないかな・・・

→一人もいない。みんな優秀だなあ。


システムテスト

→Passed


以下、ソースです。

class RouteIntersection {
public:
	string isValid(int N, vector <int> coords, string moves) {
		string res;
		int ps=coords.size();
		vector <int> co(ps, 0);
		set <vector <int> > st;
		map <int, int> cotoi;

		int id=0;
		for(int i=0; i<ps; i++) {
			if(!cotoi.count(coords[i])) cotoi[coords[i]]=id++;
		}

		st.insert(co);
		for(int i=0; i<ps; i++) {
			if(moves[i]=='+') co[cotoi[coords[i]]]++;
			else co[cotoi[coords[i]]]--;
			st.insert(co);
		}

		if((int)st.size()<ps+1) res="NOT VALID";
		else res="VALID";

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