ABC238_D – AND and SUM

プログラミング

2023.08.30

ABC238_D – AND and SUM

問題
提出
1. 3回目くらいで解けた

問題

D - AND and SUM

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

提出

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.

3回目くらいで解けた

以下、解法を書く。

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

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

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

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

$x_{i} X O R y_{i}$	$x_{i} A N D y_{i}$	x_i	y_i
0	0	0	0
0	1	0 or 1	1 or 0
1	0	1	1
1	1	×	×

両方 $1$ の時の場合のみ、 $x_{i}, y_{i}$ は存在しない。
全てのビットを同時に計算することを考えると、 $(x_{i} X O R y_{i}) A N D (x A N D y)$ が0の時”Yes”になる。