Codeforces #280 Div2 D. Vanya and Computer Game

EよりDの方が難しかった…。
http://codeforces.com/contest/492/problem/D

問題

２人でA[i]体のモンスターを倒したい。
１人目は１秒にX体、すなわち1/X秒に１体モンスターを倒す。
２人目は１秒にY体、すなわち1/Y秒に１体モンスターを倒す。

A[i]体目のモンスターを倒すのはどちらか、もしくは２人同時か答えよ。

解法

まずXとYが互いに素になるよう、最大公約数で割っておく。
すると、２人同時にモンスターを倒すのは1秒毎である。

１秒に倒すモンスターは(X+Y)体で、(X+Y-1)体目と(X+Y)体目は２人で同時で倒す。
よってまずはA[i]%(X+Y)を求めておき、0か(X+Y-1)なら答えは２人同時である。
それ以外、A[i]%(X+Y)≦X+Y-2なら、２人のどちらかが倒す。

ここから先は２つの解法がある。
１つ目は、(X+Y)体のモンスターを倒す順番を列挙する方法である。
これは２人がモンスターを倒すタイミング1/X、2/X、3/X…と1/Y、2/Y、3/Y…を合わせてソートすれば、何体目をどちらが倒すかわかる。

自分は二分探索を用いた。
時間に対して倒せる敵の数を二分探索し、A[i]%(X+Y)体目を倒す時間T1と(A[i]%(X+Y)-1)体目を倒す時間T2を求める。
すると、T1とT2の間には１人目と２人目どちらかだけが敵を倒すことになるので、それがどちらかを求める。
小数の除算は精度が怖いので、1/(XY)単位で時間を計算すると、整数演算だけで済む。

int N;
ll X,Y,A[100200];

ll num(ll tim) {
	return tim/X + tim/Y;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	ll g=__gcd(X,Y);
	X/=g;
	Y/=g;
	while(N--) {
		cin>>r;
		
		r %= X+Y;
		if(r==0 || r==X+Y-1) cout<<"Both"<<endl;
		else {
			ll tim=0,tim2=0;
			for(i=39;i>=0;i--) if(num(tim+(1LL<<i))<=r-1) tim +=(1LL<<i);
			for(i=39;i>=0;i--) if(num(tim2+(1LL<<i))<=r) tim2 +=(1LL<<i);
			
			if(tim/Y!=tim2/Y) cout<<"Vanya"<<endl;
			else cout<<"Vova"<<endl;
		}
	}
}

まとめ

1秒毎に２人同時にモンスターを倒す際、カウントが２でなく１になると思ってしまいWAしてしまった。