ABC238D

ABC238D の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc238/submissions/29106574

問題

2つの数字 a, s が与えられて
x AND y = a
x + y = s
を満たす（x, y）の組みが非負整数で存在するかどうかを調べる問題です．

解説

模範解答がどのような仕組みで計算されているのかを解説していこうと思います．

概要と例1（a=1, s=8）についてです．

ABC238D_ex1

ANDが aになる必要があることから，aが1になっている桁のみで，すでに和が2aになることがわかります．

このとき，aが1になっていない桁のみで，x + y = s-2a になれば，条件を満たすことになります．

うまくいかない例を示します．

ABC238D_ex2

a = 1, s = 7のとき，s-2a = 5 は，bitで 0101になりますが，
この 0101 の1の位が1であることは，
x AND y = a を満たしながら，x + y = 7 を満たすには，
1の位が片方が1の組み合わせである必要があることを示しています．

しかし，x AND y = 1 を満たすには，1の位は共に1である必要があるため，
同時に満たすことができません．

すなわち，このような解は存在しないことを意味します．

上記の内容をコードにします．

標準入力を読み取ります．

T = int(input())

T回ループを回して，題意を満たすための条件を満たすかどうかを判定すればよいです．

for _ in range(T):
    a, s = map(int, input().split())
    # 非負整数の組みをもつことより
    flg1 = s - 2*a >= 0
    # 片方のみ1になる必要ある桁（s-2a）と両方1になる必要がある桁（a）の論理和はゼロ
    flg2 = (s - 2*a)&a == 0
    if flg1 and flg2:
        print('Yes')
    else:
        print('No')

以上，ABC238Dの解法でした．

＜参考解説リンク＞

1) 【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！ - Qiita