AtCoder Beginner Contest 238 - D AND and SUM なんとなく解説

はじめに

コンテスト時に発想した内容をメモしておこうと思います。結局解説と同じような話・・・のはず。もし嘘回答とかなら教えてください。

コード

Python

T = int(input())

ret = []
for i in range(T):
    a, s = map(int, input().split())
    x = a
    y = s - a
    if y >= 0 and (x & y) == a:
        ret.append("Yes")
    else:
        ret.append("No")

print(*ret, sep="\n")

回答時は下記。ただ余計なコードが多いので、上記は整理したものになります。

整理

入力例1の一つ目のクエリについて考えます。

a=1
s=8

まず、ANDのほうに着目します。

a=1=0x0001　#変則2進数表記、後続の説明のため2進数を左からゼロ埋めしています

ということは
一番右のbitはxもyも1になるはずです。
一方、それ以外のbitはどちらかが1、もしくは0になるはずです。

もし上記の状態のビットを?と書くならば、x,yはそれぞれ下記の通りになります。

x=0x???1 y=0x???1

#?の条件を満たす組み合わせの例、ただし問題全体の条件を満たすものとは限らない
x=0x0101 y=0x0001
x=0x1101 y=0x0011
x=0x1001 y=0x0001
x=0x0001 y=0x1011

さて、xとyにおいてある桁の?の中身が両方0もしくはどちらかが1なわけですが、
どちらに1が立っていたとしてもx+yは変わりません。

であれば、xの?は0に決めてしまって、yだけに?を残すようにしましょう。すなわち、

x=0x0001 y=0x???1

こうすると、x=aになります。

この情報を用いて、sとaの条件を満たすか確認していきましょう。

s=x+y => y=s-x

となるので、x=aを代入すると

y=s-a

になります。この時点でこのxとyはsの条件を満たします。
ただし、yがマイナスにならないようにチェックが必要になります。

次に、aの条件を満たすか確認しましょう。具体的には、

x & y = a & (s-a)

これがaと一致するか否かチェックしてあげればOKです。

メモ

Pythonの&とANDは違う