Google Code Jam 2015 Round 1A : B. Haircut

こちらは問題文がシンプルで良かった。
https://code.google.com/codejam/contest/4224486/dashboard#s=p1

問題

B個の床屋がある。
各床屋は時刻0に開店し、並んだ客を処理していく。
各床屋は1人を時間M[i]で処理できる。

客は一列に並んでおり、先頭から床屋に空きができ次第そこに入る。
同時に複数空きができた場合、番号の小さい床屋に入る。

列のN番目の人はどの床屋に入ることになるか答えよ。

解法

N番目の人が床屋に入る時刻Tを二分探索すればよい。
時刻Tまでに床屋に入る人f(T)=sum(T/M[i]+1)なのでO(B)で計算できる。

N-f(T-1)人は時刻T以前に床屋に入り終わっているので、後はT%M[i]==0となる(N-f(T-1))個目の床屋を答えればよい。

int B,M[1010];
ll N;

ll numnum(ll tim) {
	ll tot=0;
	int i;
	if(tim<0) return 0;
	FOR(i,B) tot+=tim/M[i]+1;
	return tot;
}


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>B>>N;
	FOR(i,B) cin>>M[i];
	
	ll tt=(1LL<<61)-1;
	for(i=60;i>=0;i--) if(numnum(tt-(1LL<<i))>=N) tt -= (1LL<<i);
	N-=numnum(tt-1);
	FOR(i,B) if(tt%M[i]==0) {
		if(--N==0) return _P("Case #%d: %d\n",_loop,i+1);
	}
	
	_P("Case #%d:\n",_loop);
}

まとめ

問題文がわかりやすい分、Aよりも短い時間で解けていたようだ。