問題はこちら
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