Codeforces ECR #010 : F. Ants on a Circle

本番中に正解の解法には辿りつけてたけど、バグが取りきれず仕舞い。
http://codeforces.com/contest/652/problem/F

問題

１周Mの円周がある。
時刻0において、円周上N匹の蟻の位置及び向きが与えられる。

蟻は時速1で向いている向きに移動する。
その際、途中で他の蟻と衝突すると両者向きを反転する。

時刻T後に各蟻がどの位置にいるかを求めよ。

解法

蟻が全員同じ向きを向くなら、永遠に衝突しないので何も考えなくて良い。
以下、初期状態で左右の向きの蟻がそれぞれ１匹以上いる場合を考える。

蟻本にある蟻の問題を参考にする。
蟻の区別をしない場合、蟻は衝突して互いに反転するのと、すれ違うのは変わらない。
よって、蟻の区別をしないならN匹の蟻がいる場所はどこか求めるのは容易である。
後は最終的にどの蟻がどの蟻の場所に移動するかを求めればよい。

まず蟻を初期位置でソートしよう。
次に初期状態で右向きの蟻Aについて考える。
蟻Aが途中左向きの蟻Bと衝突すると、元蟻Aが通ってきた移動経路は、以後Bが引き継いで同様に右方向に移動する。
すなわち、左向きの蟻1体とぶつかる度、1つ右側にいる蟻が(蟻Aが他の蟻をすり抜けて移動した場合の)移動経路を引き継ぐ。
よってAが時刻Tの間に左向きの蟻とx回ぶつかるならば、最終的に蟻Aが他の蟻をすり抜けて移動した場合の位置には、元々Aよりx個右にいる蟻が来る。
xは左向きの蟻群の座標をもとにlower_bound等を用いて求めよう。

左向きの蟻についても同様に処理できる。

int N;
ll M,T;
int S[303030],NS[303030],ret[303030];
int D[303030];
int O[303030];
int NL,NR;
pair<int,int> P[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>T;
	vector<int> VL,VR;
	FOR(i,N) {
		cin>>S[i]>>s;
		S[i]--;
		D[i]=s[0]=='R';
		if(D[i]==0) {
			NL++;
			VL.push_back(S[i]),VL.push_back(S[i]+M);
			NS[i]=(M+(S[i]-T)%M)%M;
		}
		else {
			NR++;
			VR.push_back(S[i]),VR.push_back(S[i]+M);
			NS[i]=(S[i]+T)%M;
		}
		
		P[i]={S[i],i};
	}
	
	if(NL==0 || NR==0) {
		FOR(i,N) _P("%d ",NS[i]+1);
		_P("\n");
		return;
	}
	
	sort(P,P+N);
	FOR(i,N) O[P[i].second]=i;
	sort(ALL(VL));
	sort(ALL(VR));
	
	FOR(i,N) {
		x=P[i].second;
		if(D[x]==0) {
			ll col=2*T/M*NR;
			int left=(int)(2*T%M);
			auto it1=lower_bound(ALL(VR),S[x]+M);
			auto it2=lower_bound(ALL(VR),S[x]+M-left);
			col += it1-it2;
			y = (N+(i-col)%N)%N;
		}
		else {
			ll col=2*T/M*NL;
			int left=(int)(2*T%M);
			auto it1=lower_bound(ALL(VL),S[x]+left+1);
			auto it2=lower_bound(ALL(VL),S[x]);
			col += it1-it2;
			y = (i+col)%N;
		}
		ret[P[y].second] = NS[x]+1;
		
	}
	
	FOR(i,N) _P("%d ",ret[i]);
	_P("\n");
}

まとめ

もうちょい本番中に解ける人いても良さそうだったけど。