Codeforces #1077 : Div1 B. Shortest Statement Ever

ちょっといまいちだった回。
https://codeforces.com/contest/2187/problem/B

問題

非負整数X,Yが与えられる。
以下を満たすP,Qの対を答えよ。

• P and Q = 0
• |X-P|+|Y-Q|が最小

解法

まずX-P≧0、Y-Q≧0の範囲で、P,Qに貪欲に各bitを割り当てるケースを考える。
次に、X-P＜0またはY-Q＜0の場合を考えるわけだが、P-XやQ-YのMSBがどのbitになるかを総当たりしよう。
残りのbitはやはり貪欲にP,Qに割り当てて行くケースを試せばよい。

int T;
ll X,Y;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>Y;
		ll A=-1,B=-1;
		ll CX=X,CY=Y;
		for(i=30;i>=0;i--) {
			if(CX>=1<<i) CX-=1<<i;
			else if(CY>=1<<i) CY-=1<<i;
		}
		A=X-CX;
		B=Y-CY;
		FOR(i,31) {
			if((X&(1<<i))==0) {
				ll V=((X>>i)+1)<<(i);
				ll CY=Y;
				ll W=0;
				for(j=30;j>=0;j--) if((V&(1<<j))==0) {
					if(CY>=(1<<j)) {
						CY-=1<<j;
						W+=1<<j;
					}
				}
				if(abs(X-A)+abs(Y-B)>abs(X-V)+abs(Y-W)) {
					A=V;
					B=W;
				}
			}
			if((Y&(1<<i))==0) {
				ll W=((Y>>i)+1)<<(i);
				ll CX=X;
				ll V=0;
				for(j=30;j>=0;j--) if((W&(1<<j))==0) {
					if(CX>=(1<<j)) {
						CX-=1<<j;
						V+=1<<j;
					}
				}
				if(abs(X-A)+abs(Y-B)>abs(X-V)+abs(Y-W)) {
					A=V;
					B=W;
				}
			}
		}
		FOR(i,31) FOR(j,31) if((X&(1<<i))==0) if((Y&(1<<j))==0) {
			ll V=((X>>i)+1)<<(i);
			ll W=((Y>>j)+1)<<(j);
			if(V&W) continue;
			if(abs(X-A)+abs(Y-B)>abs(X-V)+abs(Y-W)) {
				A=V;
				B=W;
			}
		}
		assert((A&B)==0);
		//cout<<abs(X-A)+abs(Y-B)<<" ";
		cout<<A<<" "<<B<<endl;
		
	}
}

まとめ

本番意外にそこまで苦労せず解いてる。