Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 238 D問題 AND and SUM

AtCoder ABC ABC238 D問題 400 pts

問題

提出解答

問題の概要

次を満たす非負整数 $x,y$ は存在するか? ただし, 2つの非負整数 $u,v$ に対して, $u \land v$ でビットごとの論理積とする.

$x+y=s$
$x \land y=a$

※ $T$ 個のマルチケース

制約

$1 \leq T \leq 10^5$
$0 \leq a,s \lt 2^{60}$

解法

まず, 和とビットごとの論理積を関連付けると等式として, 2つの非負整数 $u,v$ に対して,

$u+v=(u \oplus v)+2 (u \land v)$

が成り立つ. ここで, $u \oplus v$ はビットごとの排他的論理和とする. よって, $x+y=s, x \land y=a$ が成り立つならば, $x \oplus y=s-2a$ でなくてはならない. よって, $x \oplus y \geq 0$ であるから, $s-2a \lt 0$ だった場合は直ちに否定的に解決される.

$m:=s-2a \geq 0$ とする. 今, $x \oplus y=m, x \land y=a$ となる $x,y$ が存在するか? ということになっているが, どちらもビットごとの演算なので, $x,y,m,a \in \{0,1\}$ としてもよい.

$x,y$ をそれぞれ動かすと,

$(x,y)=(0,0)$ のとき, $(x \oplus y, x \land y)=(0,0)$
$(x,y)=(0,1)$ のとき, $(x \oplus y, x \land y)=(1,0)$
$(x,y)=(1,0)$ のとき, $(x \oplus y, x \land y)=(1,0)$
$(x,y)=(1,1)$ のとき, $(x \oplus y, x \land y)=(0,1)$

となる. よって, $x \oplus y=m, x \land y=a$ となる $x,y \in \{0,1\}$ が存在することと, $(m,a) \neq (1,1)$ であることが同値である.

よって, 各ビットごとに $(m,a) \neq (1,1)$ かどうかを見れば良い.

今, 必要条件を述べたが, 各ビットごとに上の条件を満たすように取ることで, 十分性も示せる.

これでも正解できるが, $(m,a) \neq (1,1) \iff m \land a=0$ を利用すれば, 全てのビットを一気に判定できる.