SRM 474 250pt: RouteIntersection

TopCoder

問題概要

N(<10^9)次元空間の原点にいる。順に、A[i]次元の値をinc(or dec)していく(命令長<50)。途中に同じ点を通ったかどうか求める問題。

考えたこと

  • (何か見たことはあるけどもはや通したかどうかとか覚えていない)
  • vectorをセットに突っ込んでいく？でもNがでかいから無理っぽい。
  • どうせほとんど0なんだから座標圧縮すれば良い。
  • 一番実装が楽なのはmapをsetに突っ込むことだろう。
  • 無事通った。

practiceで通ったコード

#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct RouteIntersection {

	string isValid(int N, vector <int> coords, string moves) {
		map<int,int> dict;
		set<map<int,int> > ss;

		//touch
		for(int i=0; i<(int)coords.size(); i++){
			dict[coords[i]] = 0;
		}

		ss.insert(dict);
		for(int i=0; i<(int)coords.size(); i++){
			dict[coords[i]] += moves[i] == '+' ? 1 : -1;
			ss.insert(dict);
		}

		return ss.size() == coords.size() + 1 ? "VALID" : "NOT VALID";
	}

};