All-Ukrainian School Olympiad in Informatics D: Plus and xor

Codeforces

問題概要

unsigned 64bit整数A,Bが与えられる。A=X+Y, B=X^Yを満たす非負整数X,Yのうち、Xが最小のものを求める問題。

解法(DP)

式変形して、A=(B^X)+Xなので、次の状態のDPで解いた。dp[i][Xのiビット目は0or1][Xのi-1ビット目は0or1][(B^X)+Xを計算したとき、下位ビットからのcarryの有無]。３つ目の[i-1ビット目は0or1]は多分要らない。dpテーブルに突っ込む値を工夫すれば３つ目はなくても復元できるはず。

想定解法

O(1)で実は解けるらしい(正確には上のDP解法もO(1)だけど。ビット数は固定として)。Y=B^Xを考えると、実はB^X=B+X(ここが理解できていない)、よってA=X+B+XよりX=(A-B)/2となるらしい。詳細はよく分かって無いので理解できたらそのとき追記する。EditorialのAとBのパリティが異なるとき解は無いと言っているのは最下位のビットが一致しないといけないということなんだろうか。
ようやく理解できたので追記。X^B!=X+Bならば、∃i s.t. Xのiビット目とBのiビット目がともに1。このとき、Y=B^XなのでYのiビット目は0。これはXの最小性に反する。何故なら、そのようなXとYのiビット目を入れ替えた数をX', Y'とすると、A=X'+Y', B=X'^Y'を満足し、更にX>X'だから。
更に追記。今までの理屈だけだとXの最小性がどこで保証されているのかよく分かっていない。
更に更に追記。等号による変形だから別にいいのか。理解できた。

感想

unsigned long long のビット演算の処理を間違えて1WA。

#include <iostream>
using namespace std;

typedef unsigned long long ulong;

ulong A, B, X, Y;
int dp[70][2][2][2];

void solve(){
	for(int i=0; i<70; i++)for(int j=0; j<2; j++)for(int k=0; k<2; k++)for(int l=0; l<2; l++){
		dp[i][j][k][l] = 0;
	}
	if((B&1) != (A&1)){
		cout << -1 << endl;
		return ;
	}
	dp[0][0][0][0] = 1;
	dp[0][1][0][0] = 1;
	for(ulong i=0; i<64; i++){
		for(ulong j=0; j<2; j++){
			for(ulong k=0; k<2; k++){
				for(ulong l=0; l<2; l++)if(dp[i][j][k][l]){
					ulong p = ((B>>i)&1)^j;
					if(((p+l+j)&1) != ((A>>i)&1)){
						dp[i][j][k][l] = 0;
						continue;
					}
					for(ulong s=0; s<2; s++){
						dp[i+1][s][j][p+l+j>=2?1:0] = 1;
					}
				}
			}
		}
	}
	if( !(dp[64][0][0][0] || dp[64][0][0][1] || dp[64][0][1][0] || dp[64][0][1][1]) ){
		cout << -1 << endl;
		return ;
	}
	for(ulong i=64; i>=1; i--){
		ulong prev;
		ulong cur = (X>>i)&1;
		if( dp[i][cur][0][0] || dp[i][cur][0][1] ){
			prev = 0;
		}
		else{
			prev = 1;
		}
		X |= (prev<<(i-1));
	}
	Y = A - X;
	if(0){
	cout << "X: ";for(int i=0; i<64; i++){
		cout << ((X>>(63-i))&1);
	}
	cout << endl;
	cout << "Y: ";for(int i=0; i<64; i++){
		cout << ((Y>>(63-i))&1);
	}
	cout << endl;
	}

	cout << X << " " << Y << endl;
}


int main(){
	cin >> A >> B;
	solve();
	return 0;
}