ALarge落としたけど、なんとかBC通して通過。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9/00000000003384ea
問題
2変数A,Bが与えられる。
これらに対し、1,2,3....を順に、A,Bのうち大きい方から減算していく(A=Bの時はAを選ぶ)。
ただし、これ以上引いたらA,Bが負になりそうなときはその前に停止する。
最後に引く値と、A,Bの値を求めよ。
解法
次に引く値をCとする。|A-B|≦Cとなると、以後はずっと両者交互に引くことになる。
そこで、まず最初|A-B|≦Cになるまでは、AとBの大きい方から1,2,3...を引くことにしよう。
これは二分探索でスピードアップできる。
その後は、A,B交互に引く作業を行うが、ここも二分探索で負になる直前を求める。
以下は安全側に倒しちょっと余計なコードを書いてある。
ll L,R; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>L>>R; ll cur=1; while(L>=10*cur && R>=10*cur) { if(L>=R+cur) { for(i=31;i>=0;i--) { ll cnt=(cur+cur+(1LL<<i)-1)*(1LL<<i)/2; if(L-cnt>=R) { L-=cnt; cur+=1LL<<i; } } continue; } else if(R>=L+cur) { for(i=30;i>=0;i--) { ll cnt=(cur+cur+(1LL<<i)-1)*(1LL<<i)/2; if(R-cnt>=L) { R-=cnt; cur+=1LL<<i; } } continue; } else if(L>=R) { for(i=31;i>=0;i--) { ll a=cur*(1LL<<i)+2*(1LL<<i)*((1LL<<i)-1)/2; ll b=a+(1LL<<i); if(L>=a && R>=b) { L-=a; R-=b; cur+=(2LL<<i); } } } else { for(i=31;i>=0;i--) { ll a=cur*(1LL<<i)+2*(1LL<<i)*((1LL<<i)-1)/2; ll b=a+(1LL<<i); if(R>=a && L>=b) { R-=a; L-=b; cur+=(2LL<<i); } } } } while(L>=cur || R>=cur) { if(L>=R) { L-=cur; cur++; } else { R-=cur; cur++; } } _P("Case #%d: %lld %lld %lld\n",_loop,cur-1,L,R); }
まとめ
Dは解いてないので、多分Cまで。