Google Code Jam 2020 Round 2 : A. Incremental House of Pancakes

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まで。