https://yukicoder.me/problems/no/683
解法
https://yukicoder.me/submissions/256949
よくある方針として「操作を逆に行えないか」という方針がある。
「f(a,b) := X=a, Y=bに到達可能か」という関数を作っていこう。
まず、a≦bとなるように変えて考えよう。
これは
a=0かつb=0なら到達できているので1
a=0であれば片方の総和を続けることで片方0, 片方が任意の数にできるので1
ここまでは特に問題ない。
1つ重要なことがあり、「操作を行ったあとはどちらか一方は必ず偶数になっている」ということである。
つまり、aもbも奇数なら到達できないので0
aもbも偶数なら、f(a-1,b/2)またはf(a/2,b-1)が到達可能なら1を返せばいい。
どちらかが奇数ならば、偶数の方を÷2して、到達可能か判定する。
計算量が心配であるが、片方の数は必ず半分になるので、O(logN)くらいで行けそうな雰囲気があり、やってみると通る。
ll A, B; //--------------------------------------------------------------------------------------------------- int f(ll a, ll b) { if (a > b) swap(a, b); if (a == 0 and b == 0) return 1; if (a == 0) return 1; if (a % 2 == 1 and b % 2 == 1) return 0; if (a % 2 == 0 and b % 2 == 0) return f(a - 1, b / 2) | f(a / 2, b - 1); if (a % 2 == 1) return f(a - 1, b / 2); if (b % 2 == 1) return f(a / 2, b - 1); assert(0); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B; if (f(A, B)) printf("Yes\n"); else printf("No\n"); }
