AtCoder Beginner Contest 238 (D - AND and SUM)

解説とは異なる解き方をしたので、備忘録代わりに書きます。コードはこちらです。

この解法は、加算で桁が繰り上がるのをどこで止めるかという視点です。

ある $a$ を二進数表記して、例えば $111000110010100$ とします。 $x$ と $y$ はaに0個以上のビットを立てた数なので $a$ 以上です。従って $x+y=s$ は $2a = 1110001100101000$ 以上です。 $2a$ は $a$ を一ビット左シフトして、最下位ビット(LSB)に0を詰めた値です。 $a$ と $2a$ のビットの並びを見比べると、 $2a$ は以下のようになっています。

 a=  111000110010100
2a= 1110001100101000
    ?^^   ?^  ? ?!
       ~~~~ ___~~

さて $x$ と $y$ の各ビットのうち $a$ で1でないビット( $x$ と $y$ のANDが1ではないビット)は、 $x$ と $y$ では少なくともどちらか一方が0です。上記のビット列で0と書いた部分です。つまり $x$ と $y$ のそれらのビットを足しても繰上りは発生しません。

このことに注目すると、 $a$ で1が連続するビット列について、 $s$ では以下が成り立ちます。

• $a$ で1が出現する最右のビットは、 $2a$ では必ず0になります(上記の !)。 $s$ でも下の桁から繰上りが無いので0のままです : 条件1
• $a$ の連続するビット1は、 $2a$ では左1ビットずれて必ず1になります(上記の ?)
• 左に1ビットはみ出した部分(上記の ?)は、 $2a$ に $x$ または $y$ を足して $s$ では0にも1にもなりますが、1が2連続以上するときにはみ出さなかった分(上記の ^)は下の桁から繰上りが無いので $s$ では1のままです。まとめると、 $a$ において1が連続nビット ($n>1$) で出現するとき、 $s$ の対応する連続上位 $n-1$ ビットも1でなければなりません : 条件2

$a$ で0が連続するビット列とその一つ左のビット ~ または _ について、 $s$ では以下が成り立ちます。

• 連続4ビットの ~~~~ については、0001b以上1000b以下の値を取ります。0000bにすることできませんし( $2a$ 由来の1bがあるので)、1001b以上にはできません( $x$ と $y$ の和は最大111bなので)
• 同様に連続3ビットの ___ は001以上100b以下、連続2ビットの ~~ は01以上10b以下になります
• 一般化すると、 $a$ において0が連続nビットで出現するとき、 $s$ の対応する一つ左のビットが1なら $s$ に対応するビットはすべて0にする必要があります。 $s$ の対応する一つ左のビットが0なら $s$ に対応するビットはすべて0であってはなりません。 : 条件3

$a=0$ なら Yes、 $2a > s$ なら No なのでそれらを除いてから、 $s$ が上記の条件1、条件2、条件3にすべて当てはまればYes、そうでなければNoを返します。C++なら std::bitset<64> で数値を表現すると実装しやすいです。