UnKoder #07 : Baton Relay

問題をちゃんと読まず手こずった。
https://www.hackerrank.com/contests/unkoder-07/challenges/baton-relay

問題

N人の人が1周Lのトラックに並んでいる。
各人は基準地からX[i]のところにおり、それぞれ速度V[i]で走れる。
なお、X[i]は昇順である。

最初は1番の人がバトンを持ち、そこからリレーの要領で走る。
すなわちバトンを持った人は次の人のところまで走り、バトンを渡して静止する。

各人が最初いた位置に1回以上戻るまでの最短時間を求めよ。

解法

愚直にシミュレートするだけの実装問題。
各人が距離Lを走るまでの時間を求めよう。

バトンが1周すると各人最低1は動くので、シミュレートは高々L*N回行えばよい。

int N,L;
double X[1010],V[1010],R[1010];
int ok[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>X[i]>>V[i];
	double ret=0;
	
	if(N==1) {
		ret=L*1.0/V[0];
	}
	else {
		int cur=0;
		while(1) {
			int ne=(cur+1)%N;
			
			if(X[ne]<=X[cur]) X[cur] -= L;
			double run=X[ne]-X[cur];
			if(count(ok,ok+N,1)==N-1 && ok[cur]==0 && R[cur]+run>=L) {
				run = L-R[cur];
				ret+=run*1.0/V[0];
				break;
			}
			
			ret+=run*1.0/V[cur];
			R[cur]+=run;
			if(R[cur]>=L) ok[cur]=1;
			X[cur]=X[ne];
			cur=ne;
		}
	}
	
	_P("%.12lf\n",ret);
}

まとめ

これO(LN)以下で解く解法もあるのかな？