Codeforces #310 Div1 D. Case of a Top Secret

若干コーナーケースがあるにせよ、Dにしては簡単な問題。
http://codeforces.com/contest/555/problem/D

問題

１次元の数直線上にN個の杭があり、その位置はX[i]である。
ここで、以下のクエリM個に答えよ。

各クエリでは、長さL[i]の紐の先に重りがついたものがA[i]番の杭に結び付けられているものとする。
この状態で重りが垂れ下がった状態から、紐がピンと張ったまま時計回りに回す。
途中紐が他の杭に当たった場合、問題文の図の通りその位置を回転の中心として重りは回り続ける。
最終的にどの杭の周りを周り続けるか答えよ。

解法

x番の杭に結ばれた長さLの紐の先の重りを回した場合、まずxの右側の杭で杭間の距離X[y]-X[x]がL以下でかつyが最大のものが存在する場合、以後y番の杭を中心として長さL-(X[y]-X[x])の紐が周り続ける、と考える。
そのようなyがない場合、今度はxの左側の杭で同様に杭間の距離X[x]-X[y]がL以下でかつyが最小のものを求める。

このようなyはsetのlower_bound等を使い求めることができる。
どちらも該当する(x以外の)yがない場合、他に引っかかる杭がないので解はx。
１回引っかかる杭を見つけるたびにLはどんどん短くなるので、いずれ条件を満たすxが見つかる。

注意点として、Lが大きいため両端の杭の距離が短い場合、２つの杭の間をO(L)回程度回ること場合がある。
こうするとTLEするので、周期的なパターンを見つけたら２杭間の往復距離の剰余を取って無駄な繰り返しを省略しよう。

int N,M;
ll X[202020],S[202020];
int A[202020],L[202020],id[202020],rid[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	X[0]=S[0]=-1LL<<31;
	X[N+1]=S[1]=1LL<<31;
	FOR(i,N) cin>>X[i+1], S[i+1]=X[i+1];
	sort(X,X+N+2);
	FOR(i,N) id[i+1]=lower_bound(X,X+(N+2),S[i+1])-X, rid[id[i+1]]=i+1;
	
	FOR(i,M) {
		cin>>x>>y;
		int pre[2]={-1,-1};
		x=id[x];
		int dir=1;
		while(1 && N>1) {
			if(pre[1]==x) y %=(X[pre[0]]-X[x])*2;
			pre[1]=pre[0];
			pre[0]=x;
			
			if(X[x]-X[x-1]>y && X[x+1]-X[x]>y) break;
			FOR(j,2) {
				if(dir==1) {
					auto it=lower_bound(X,X+(N+2),X[x]+y+1);
					
					it--;
					if(*it!=X[x]) {
						y -= *it-X[x];
						x = it-X;
						dir=0;
						break;
					}
				}
				else {
					auto it=lower_bound(X,X+(N+2),X[x]-y);
					
					if(*it!=X[x]) {
						y -= X[x]-*it;
						x = it-X;
						dir=1;
						break;
					}
				}
				dir^=1;
			}
			
		}
		_P("%d\n",rid[x]);
	}
	
}

まとめ

Lが大きいと何周もする場合がある、という点だけ気を付ければ簡単。
Div1 Bでもいい位。