なんとか本番に解けた。
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); } }
まとめ
若干ややこしいコードだけど、何とか解ききれてよかった。