こんにちは, Ruteです.
普段は, ABC級コンテスト終了後にYouTubeにて「振り返り配信」と題してコンテストの問題の振り返りを視聴者と双方向型で行う配信を行っています.
この記事では, ABC238のD問題「AND and SUM」に関して図を用いた解説を行います.
理由としては, 公式解説が数式を中心にした解説で, 図などを用いた明瞭な解説では無かったためです.
(この文章が, 解説には図を必要とする という強い主張が入っているわけではありません)
では, 早速問題を見ていきましょう.
#1. 問題内容
ABC238 D問題「AND and SUM」
問題文
$T$個のテストケースについて, 以下の問題を解いて下さい.
非負整数$a,s$が与えられます. この時, 以下の条件を満たす非負整数の組$(x,y)$は存在しますか？
- $ x\hspace{2pt} AND\hspace{2pt} y = a$
- $ x + y = s$
制約
- $1 \leq T \leq 10^{5}$
- $0 \leq a,s < 2^{60}$
#2. 解説
2-1. 1番目の条件
まず,この問題の1番目の条件について考えてみましょう.
(以降,$x,y,a$について,2進法表記した際の$k$ケタ目の数字をそれぞれ$x[k],y[k],a[k]$と表現します.)
$x\hspace{2pt} AND\hspace{2pt} y =a$より,
$a[k]$ = 1 の場合
- $x[k] = 1$ かつ $y[k] = 1$
$a[k]$ = 0 の場合
- $x[k] = 1$ かつ $y[k] = 0$
- $x[k] = 0$ かつ $y[k] = 1$
- $x[k] = 0$ かつ $y[k] = 0$
のいずれかとなります.
また, このことから$x$と$y$の値は$a$以上であることが分かります.
<証明>
$a[k] = 1$では無い部分では,$x[k],y[k]$の数字が確定できない.
ここで, 確定していない$x[k],y[k]$の数字を全て$0$であると仮定すると, $x,y$の値は$a$となる.
したがって, $x$と$y$は$a$以上であることが示された.
2-2. 2番目の条件
次に, この問題の2番目の条件について考えてみましょう.
s < 2aの場合
まず, $x + y \leq 2a$ですから, $s < 2a $の場合両方の条件を満たす非負整数の組$(x,y)$は存在しません.
2a ≦ s の場合
$2a = s$の場合は, $x,y$を2進数表記したものについて$1$と確定していない桁を全て$0$とすると,$(x,y) = (a,a)$で条件を満たします.
$2a < s$の場合について考えましょう.
$x,y$を2進数表記した際, 確定していない桁について,
1番目の条件より
$x[k]$または$y[k]$のどちらかの数字が0
あるいは$x[k] = 0$かつ$y[k] = 0$
である必要があります.
そこで,以下の問題を考えます.
$x,y$を2進法表記した際に確定していない桁の数字について,そのどちらかを$1$にすることにより,$x + y = s$にすることが可能か.
これは, 上の桁から貪欲的に以下の問題を解くことにより, 解くことが可能です.
$L$の初期値を$s - 2a$とする.
もし$L \geq 2^{k}$であれば, $L$から$2^{k}$を減算する.
最終的に$L = 0$ならば,$x + y = s$にすることが可能.
$L > 0$ならば, $x + y = s$にすることは不可能.
この問題に対する答えの導出は, $O(Tmax(\log_{2}{s}))$程度で計算することが可能です.
これは制約の範囲では高々$600万$程度となり, 実行時間2秒以内に計算することが可能です.
#3. ソースコード
以下, Pythonによるソースコードを示します.
Pythonの解答例
T = int(input())
for i in range(T):
a,s = map(int,input().split())
if 2 * a > s:
print("No")
elif 2 * a == s:
print("Yes")
else:
t = s - 2 * a
k = bin(a)
k = k[2:len(k)]
m = k.zfill(60)
#62桁までゼロ埋めする.
now_t = t
for i in range(59,-1,-1):
if m[-(i+1)] == "1":
continue
else:
if 2 ** i <= now_t:
now_t -= 2 ** i
if now_t != 0:
print("No")
else:
print("Yes")
解説は以上となります.
不明な点, 補足した方が良い点などありましたらコメントをお願いします.
よろしければ, LGTMや拡散をしていただけると嬉しいです！
また, 私のYouTubeチャンネル「Ruteチャンネル」では, 先述した通りの「振り返り配信」をABC級コンテスト終了後に行っています. よろしければ, 以下のURLからチャンネルを見て頂けると嬉しいです！