メモ

yukicoderでゆるふわgolf

yukicoder No.683 Two Operations No.3

問題はこちら
No.683 Two Operations No.3 - yukicoder

逆向きに再帰で全探索すると解ける。

int f(long x,long y){
	if(x==0||y==0)return 1;
	int flag=0;
	if(x%2==0)flag|=f(x/2,y-1);
	if(y%2==0)flag|=f(x-1,y/2);
	return flag;
}

int main(){
	long x,y;
	scanf("%ld%ld",&x,&y);
	puts(f(x,y)?"Yes":"No");
}

現実的には探索回数は十分小さくなるらしいが、ここでは√N以下になることを示す。
(この証明はwriterに教えていただいた)
(証明)
mod 4で考える。
X,Yがともに4の倍数であるとき以外は、遷移先が一意に決まることが分かる。
また、X,Yがともに4の倍数のときは
(00,00)→(00,11)→(00,10)→(00,01)→(00,00)
(00,00)→(10,11)→(01,10)→(00,01)→(00,00)
のどちらかの遷移をたどったときその時に限り、ともに4の倍数である状態に戻ってくる。
よって、探索の枝は深さ4毎に高々2倍になる。ここで深さ1ごとにXYは1/2より小さくなるので、探索の深さは高々log2(XY)≦2log2(N)。
探索回数は高々2^(2log2(N)/4)=√Nである。
(証明終わり)
なお実際には√N=10^9どころか、せいぜい10^3程度にしかならないようである

フラグの持ち方を少し工夫して

F;
f(long x,long y){
	x&&y?x%2||f(x/2,y-1),y%2||f(x-1,y/2):F++;
}
main(){
	long x,y;
	scanf("%ld%ld",&x,&y);
	f(x,y);
	puts(F?"Yes":"No");
}

126B