ABC238D - AND and SUM、ANDとORに読み替える解法
問題
解説
$ \text{AND} と $ + で表された条件を $ \text{AND} と $ \text{OR} に読み替えて解く方法について解説します。
まずビット演算全般について、それぞれ「ビットごとに ○○ する演算」と言い換えられます。
○○ の部分は、例えば
$ \text{AND}:$ \min、$ \bmod \, 2 での積
$ \text{OR} :$ \max
$ \text{XOR}:$ \bmod \, 2 での和
$ \text{NOT}:$ \bmod \, 2 での $ +1
となります。
今回は $ \text{AND}:$ \min、$ \text{OR}:$ \max の解釈を利用します。
さて、$ \min と $ \max と $ + については、恒等式
$ \min(p, q) + \max(p, q) = p + q
が成り立ちます。
「小さい方 $ + 大きい方 $ = 和」という当たり前の式ですね。
これをビットごとに適用してやると、恒等式
$ (x \: \text{AND} \: y) + (x \: \text{OR} \: y) = x + y
が得られます。
先の恒等式より，問題文で与えられた $ (x, y) に関する条件
$ x \: \text{AND} \: y = a
$ x + y = s
は、$ a \le s ならば、$ \text{AND} と $ \text{OR} を用いた式
$ x \: \text{AND} \: y = a
$ x \: \text{OR} \: y = s - a
に変形できます。（同時に、$ a \gt s のときは条件が満たされないことも分かります。）
書き換えた後の条件を満たすような $ (x, y) が存在するかどうかを考えましょう。
以下便宜上 $ b = s - a とおきます。また $ x の第 $ i ビットを $ x \lbrack i \rbrack などと書くことにします。
再び $ \text{AND}:$ \min、$ \text{OR}:$ \max の解釈を用います。
条件を満たすためには，各第 $ i ビットについて、小さい方が $ a \lbrack i \rbrack、大きい方が $ b \lbrack i \rbrack になるようなビットの組 $ (x \lbrack i \rbrack, y \lbrack i \rbrack) が存在すれば良いです。
このような組は $ a \lbrack i \rbrack \le b \lbrack i \rbrack であるときに限り存在します。
（例えば $ (x \lbrack i \rbrack, y \lbrack i \rbrack) = (a \lbrack i \rbrack, b \lbrack i \rbrack) とすれば良いです。）
よって条件は全てのビットで $ a \lbrack i \rbrack \le b \lbrack i \rbrack が成り立つことと言い換えられます。
さらにこの不等式を $ \min (a \lbrack i \rbrack,b \lbrack i \rbrack) = a \lbrack i \rbrack と書き直して全てのビットについてまとめれば、$ a \: \text{AND} \: b = a、すなわち $ a \: \text{AND} \: (s - a) = a と書き直せます。
以上より、
$ a \le s
$ a \: \text{AND} \: (s - a) = a
であれば Yes、さもなくば No を出力すれば良いです。
提出
元ポスト