TopCoderOpen 2018 Round4 Medium PolylineAreas

方針はあっていたのにもったいない。
http://community.topcoder.com/stat?c=problem_statement&pm=14993

問題

２次元座標上を、ロボットが下記コマンドに応じて動くことを考える。

• 1だけ前方に進む。
• 90度だけ左右に向きを変える。

ロボットがたどった軌跡のうち、閉じた図形があればその面積を列挙せよ。

解法

まずロボットの移動経路が妙な形式で渡されるのでパースする。
空文字に対し10^6回の繰り返しを要求するようなケースがあるが、その際は繰り返しを行わないようにする。
その後はロボットを実際に動かし、移動経路、すなわち格子点同士を結ぶ辺を列挙する。

次に閉じた図形を探索しよう。
これは迷路探索における左手法の要領で行う。各辺に対し右側を辿っていき、１周したらその面積を求める。
1点問題があって、同じ図形の内側を辿る場合と外側を辿る場合で面積が２重にカウントされるケースがある。
そこで内側だけたどる場合のみ解に加えたい。

よって、最終的な結果から面積が最大の要素を取り除こう。
描く軌跡は連結なので、最大面積の要素が一番外側を辿ったケースを判断できる。

なお、TopCoderの環境では辺を辿る作業を再帰で行うとSEGVで落ちたので、わざわざループに差し替えた。

map<pair<int,int>,int> mask;
map<pair<int,int>,int> did;
vector<pair<int,int>> P;
vector<ll> cand;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


class PolylineAreas {
	public:
	string S,C;
	int step;
	
	string inst(string& S) {
		string cmd;
		if(S.back()=='[') {
			S.pop_back();
			cmd=program(S);
			assert(S.back()==']');
			S.pop_back();
		}
		else {
			cmd=S.substr(S.size()-1);
			S.pop_back();
		}
		return cmd;
	}
	string program(string& S) {
		if(S.empty()) return "";
		if(S.back()==']') return "";
		string cmd;
		if(S.back()>='0' && S.back()<='9') {
			int num=0;
			while(S.back()>='0' && S.back()<='9') {
				num=num*10+(S.back()-'0');
				S.pop_back();
			}
			string s=inst(S);
			if(s.size()) {
				while(num--) cmd+=s;
			}
		}
		else {
			cmd=inst(S);
		}
		
		return cmd+program(S);
	}
	
	vector<long long> findAreas(string polyline) {
		S=polyline;
		reverse(ALL(S));
		C=program(S);
		
		int X=0,Y=0;
		int d=0;
		int i,j;
		mask.clear();
		FORR(c,C) {
			if(c=='L') d++;
			if(c=='R') d+=3;
			d%=4;
			if(c=='F') {
				mask[{X,Y}] |= 1<<(d%4);
				did[{X,Y}]=0;
				X+=dx[d%4];
				Y+=dy[d%4];
				mask[{X,Y}] |= 1<<((d+2)%4);
				did[{X,Y}]=0;
			}
		}
		
		cand.clear();
		FORR(m,mask) {
			FOR(i,4) if((m.second&(1<<i)) && ((did[m.first] & (1<<i))==0)) {
				step++;
				P.clear();
				int X=m.first.first,Y=m.first.second;
				int dir=i+1;
				while(1) {
					P.push_back({X,Y});
					dir+=3;
					dir%=4;
					while((mask[{X,Y}] & (1<<dir))==0) dir=(dir+1)%4;
					if(did[{X,Y}] & (1<<dir)) break;
					did[{X,Y}] |= 1<<dir;
					int nx=X+dx[dir];
					int ny=Y+dy[dir];
					X=nx;
					Y=ny;
				}
				
				ll area=0;
				FOR(j,(int)P.size()-1) area += 1LL*P[j].first*P[j+1].second-1LL*P[j].second*P[j+1].first;
				if(area) cand.push_back(abs(area)/2);
			}
		}
		
		sort(ALL(cand));
		if(cand.size()) cand.pop_back();
		if(cand.size()>200) {
			vector<ll> ret;
			FOR(i,100) ret.push_back(cand[i]), ret.push_back(cand[cand.size()-1-i]);
			sort(ALL(ret));
			cand=ret;
		}
		
		return cand;
	}
}

まとめ

SEGVは勘弁してほしい…。