geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC238 参加記録

ABC XOR ビット演算

コンテスト中AC: A〜D

A - Exponential or Quadratic
D - AND and SUM
- 公式解説メモ
- 連立方程式の解き方

A - Exponential or Quadratic

$n\leq 10^9$ から、 $2^n$ が64bit整数型に収まらなければ、直ちにYesです。
よって、64bit型を超えるまでは、実際に2を掛けていきます。そして、超えた時点でYesとします。
超えなかった場合は、実際に比較してみれば良いです。

2を掛ける最大回数は、おそらく64くらいだと思います。
オーバーフローの判定はC++(GCC?)なら、__builtin_sumlll_overflowでできます。
提出コード

D - AND and SUM

$a_i$ という風に表記したとき、2進数の下からiビット目とします。

$a_i=1$ の時、 $(x_i,y_i)=(1,1)$ とするしかありません。
$a_i=0$ の時、 $(x_i,y_i)=(0,1),(1,0),(0,0)$ の3パターンがあり得ます。少なくとも一方は0にする必要があり、それはどちらでも良いので、 $x_i = 0$ と仮定しておきます。この時、 $x = a$ となります。

$a_i,s_i$ 及び桁上がり $u$ によって、以下のように下の桁から順に、 $y_i$ を決定、もしくは、達成可能か決定できます。

$a_i=1$ の場合
このケースでは $(x_i,y_i)=(1,1)$ で、桁上がりが必ず発生します。
- $u=1$ の場合
  $(1,1)$ と桁上がり1を計算すると、1+1+1 = 11になります。
  - $s_i = 0$ の場合、計算結果と一致しないのでNoです。
  - $s_i = 1$ の場合、矛盾しないので問題ないです。
- $u=0$ の場合
  $(1,1)$ と桁上がり0を計算すると、1+1+0 = 10になります。
  - $s_i = 0$ の場合、矛盾しないので問題ないです。
  - $s_i = 1$ の場合、計算結果と一致しないのでNoです。
$a_i=0$
このケースでは $(x_i,y_i)=(0,?)$ です。
- $u=1$ の場合
  - $s_i = 0$ の場合、 $y_i = 1$ とします。0+1+1=10で、桁上がりが発生します。
  - $s_i = 1$ の場合、 $y_i = 0$ とします。0+0+1=01です。
- $u=0$ の場合
  - $s_i = 0$ の場合、 $y_i = 0$ とします。0+0+0=00です。
  - $s_i = 1$ の場合、 $y_i = 1$ とします。0+1+0=01です。

なお、十分に大きい桁(今回なら制約上60桁目)まで、上記処理を行った後、桁上がりが残っていた場合もNoになります。

提出コード

公式解説メモ

$x + y = x\ XOR\ y + 2(x\ XOR\ y)$

より、

$s = x\ XOR\ y + 2a$

$x\ XOR\ y = s - 2a$

$x\ XOR\ y \geq 0$ より、 $s-2a \geq 0$ を満たしていなければNo

$b = s-2a$ とおく。

$\begin{equation} x\ AND\ y = a \\ x\ XOR\ y = b \\ \end{equation}$

という連立方程式を解く問題となる。桁上がりは不要で、各bitのみを見れば良い。
$a_i = 1 \wedge b_i = 1$ となるbitがあると、達成できずNoとなる。
よって、 $a\ AND\ b = 0$ となるかどうかで判定ができる。

連立方程式の解き方

$x=a$ を仮定すると、 $a\ XOR\ y = b$ より、両辺のa XORを取ると、

$y = a\ XOR\ b$

となるので、 $a\ AND\ y=a$ より、

$a\ AND\ (a\ XOR\ b) = a$

を満たせば良いです。

公式解説は、 $a_i,b_i$ の組が4通りの考慮が必要で、更にそこからa AND b = 0という条件を導き出さないといけないので、それよりは多少楽かなと思いました。

提出コード