ABC238_D – AND and SUM

問題

D - AND and SUM

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #45055842 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 238）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

3回目くらいで解けた

以下、解法を書く。

$x+y=s$を論理式を使ってかくと、$(x XOR y)+2(x AND y) = s$となることを使う。
式変形の意図を書いてみる。
$x XOR y $は繰り上がりなしで考えた場合の和を表し、$2(x AND y)$は繰り上がりを表す。
$(x AND y)$は$x,y$が$1$の時のみ$1$なので、次の桁に繰り上がりがあることを表す。

次に上記の式に$x AND y = a$を代入してみると、以下ののようになる。
$$(x XOR y)+2a = s$$
$$(x XOR y)= s-2a$$

ここで、$x,y$は非負整数なので、$(x XOR y )=>0$であり、$s-2a=>0$となる必要がある。
つまり、$s-2a<0$の場合は”No”が答えになる。

$(x XOR y )=>0$の時、$(x XOR y)= s-2a$と$x AND y = a$が同時に成り立てば”Yes”になり、それ以外は”No”になる。
$i$番目のビットを確認することを考えと、以下の表のようになる。

両方$1$の時の場合のみ、$x_i,y_i$は存在しない。
全てのビットを同時に計算することを考えると、$(x_i XOR y_i) AND (x AND y)$が0の時”Yes”になる。