kmjp's blog

競技プログラミング参加記です

New Year Contest 2015 : G - ロボット

なんとか本番に解けた。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_7

問題

2次元座標上にN体のロボットがいる。
各ロボットは上下左右のいずれかを向いて止まっている。
ロボットは何かが触れるとその向きに速度1で進む。

時刻0にプレイヤーが0番のロボットに触れた場合、時刻Tの各ロボットの位置を答えよ。

解法

座標圧縮してダイクストラを行い、各ロボットが動作し始める時間を求めればよい。
なお、上向きのロボットが他の上向きのロボットに触れた場合、以後その2体は同じタイミングで動く。
そのため片方はそれ以上探索する必要はない。

int N;
ll T,X[101000],Y[101000];
char M[101000];
ll ST[101000];
map<int,int> XM,YM;
map<int,int> HL[101000],VL[1010000];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>M[i];
		ST[i]=1LL<<60;
		XM[X[i]]=YM[Y[i]]=0;
	}
	x=0; ITR(it,XM) it->second=x++;
	x=0; ITR(it,YM) it->second=x++;
	FOR(i,N) {
		HL[YM[Y[i]]][X[i]]=i;
		VL[XM[X[i]]][Y[i]]=i;
	}
	
	ST[0]=0;
	priority_queue<pair<ll,int> > Q;
	Q.push(make_pair(0,0));
	while(Q.size()) {
		ll ct=-Q.top().first;
		int k=Q.top().second;
		Q.pop();
		if(ct!=ST[k]) continue;
		HL[YM[Y[k]]].erase(X[k]);
		VL[XM[X[k]]].erase(Y[k]);
		
		map<int,int>::iterator it;
		if(M[k]=='U') {
			for(it=VL[XM[X[k]]].lower_bound(Y[k]); it!=VL[XM[X[k]]].end();it++) {
				ll nt=ST[k]+abs(Y[it->second]-Y[k]);
				if(nt<ST[it->second]) {
					ST[it->second]=nt;
					Q.push(make_pair(-nt,it->second));
				}
				if(M[it->second]==M[k]) break;
			}
		}
		if(M[k]=='D') {
			for(it=VL[XM[X[k]]].lower_bound(Y[k]);it!=VL[XM[X[k]]].begin();) {
				it--;
				ll nt=ST[k]+abs(Y[it->second]-Y[k]);
				if(nt<ST[it->second]) {
					ST[it->second]=nt;
					Q.push(make_pair(-nt,it->second));
				}
				if(M[it->second]==M[k]) break;
			}
		}
		if(M[k]=='L') {
			for(it=HL[YM[Y[k]]].lower_bound(X[k]);it!=HL[YM[Y[k]]].begin();) {
				it--;
				ll nt=ST[k]+abs(X[it->second]-X[k]);
				if(nt<ST[it->second]) {
					ST[it->second]=nt;
					Q.push(make_pair(-nt,it->second));
				}
				if(M[it->second]==M[k]) break;
			}
		}
		if(M[k]=='R') {
			for(it=HL[YM[Y[k]]].lower_bound(X[k]); it!=HL[YM[Y[k]]].end();it++) {
				ll nt=ST[k]+abs(X[it->second]-X[k]);
				if(nt<ST[it->second]) {
					ST[it->second]=nt;
					Q.push(make_pair(-nt,it->second));
				}
				if(M[it->second]==M[k]) break;
			}
		}
		
	}
	
	
	FOR(i,N) {
		ll xx=X[i],yy=Y[i];
		if(M[i]=='U') yy+=max(0LL,T-ST[i]);
		if(M[i]=='D') yy-=max(0LL,T-ST[i]);
		if(M[i]=='L') xx-=max(0LL,T-ST[i]);
		if(M[i]=='R') xx+=max(0LL,T-ST[i]);
		_P("%lld %lld\n",xx,yy);
	}
	
}

まとめ

若干ややこしいコードだけど、何とか解ききれてよかった。