EよりDの方が難しかった…。
http://codeforces.com/contest/492/problem/D
問題
2人でA[i]体のモンスターを倒したい。
1人目は1秒にX体、すなわち1/X秒に1体モンスターを倒す。
2人目は1秒にY体、すなわち1/Y秒に1体モンスターを倒す。
A[i]体目のモンスターを倒すのはどちらか、もしくは2人同時か答えよ。
解法
まずXとYが互いに素になるよう、最大公約数で割っておく。
すると、2人同時にモンスターを倒すのは1秒毎である。
1秒に倒すモンスターは(X+Y)体で、(X+Y-1)体目と(X+Y)体目は2人で同時で倒す。
よってまずはA[i]%(X+Y)を求めておき、0か(X+Y-1)なら答えは2人同時である。
それ以外、A[i]%(X+Y)≦X+Y-2なら、2人のどちらかが倒す。
ここから先は2つの解法がある。
1つ目は、(X+Y)体のモンスターを倒す順番を列挙する方法である。
これは2人がモンスターを倒すタイミング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人目と2人目どちらかだけが敵を倒すことになるので、それがどちらかを求める。
小数の除算は精度が怖いので、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秒毎に2人同時にモンスターを倒す際、カウントが2でなく1になると思ってしまいWAしてしまった。