ABC050 D - Xor Sum - ツバサの備忘録

問題
 提出コード
方針がたってから遷移をバグなく求めるまでになんと半日かかりました！

解法

桁DPです。
というのも、2進数になおした2つの数字のペア $(a,b)$ について、それぞれの桁についてありうる桁の組み合わせは、
$(0,0), (0,1), (1,1)$
の3種類のみです。
そして、これらの組み合わせが、そのまま $(v,u)$ の組み合わせになります。
$xor$ については、 $(0,0)$ と $(1,1)$ ではどちらも0になりますが、 $(1,1)$ のパターンは、 $+$ をしたときにくりあがりをするため、 $(0,0)$ とは値が必ず異なります。
ということで、 $(0,0),(0,1),(1,1)$ の3種類の組み合わせを $(a,b)$ のそれぞれの桁に当てはめていったときに、 $a+b$ が $N$ を下回るものの個数を求めれば、答えになります( $a xor b$ はかならず $a + b$ 以下になるので、これ以降は $xor$ について考察をする必要はなくなります)。
ということで、 $(a,b)$ の組み合わせの中で、 $max(a,b)$ が最大となるのは、 $(a,b)=(N,0)$ のときになるので、 $N$ を2進数に直した場合の桁数だけ、3種類のビットの組み合わせを当てはめていきます。
$dp[i][j][k]$ とします。

$i$ :左から今 $i$ 桁目を見ている、という情報です。
$j$ : $i+1$ 桁目でくりあがりが行われたかどうか、という情報です。真なら1、偽なら0です。
$k$ :今作成している $(a,b)$ は、 $a+b \lt N$ となることが確定しているかどうか、という情報です。真なら1、偽なら0です。

初期状態は、
$dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = 1$
となります。これはそれぞれ、 $0$ 桁目で $(0,1)$ を選んだパターン( $1$ 桁目の繰り上がりなし)、 $i$ 桁目で $(0,0)$ を選んだパターン( $1$ 桁目の繰り上がりなし)、 $i$ 桁目で $(0,0)$ を選んだパターン( $1$ 桁目の繰り上がりあり)、の3つのパターンに対応します。

ここからは、0-indexedで考えていきます。例えば、2進数で110という数字は、左から0桁目と1桁目が'1'、2桁目が'0'です。
遷移の個数がかなり多いです。

$N$ の $i$ 桁目が0か1か
$(a,b)$ の $i$ 桁目の組み合わせをどれにするか
$i-1$ 桁目の時点で $j$ がどうだったか
$i$ 桁目の $j$ がどうなるか

によって遷移が決まります。 $N$ の $i$ 桁目が0か1か、についてまずは考えていきます。

$N$ の $i$ 桁目が'1'
$i-1$ の時点で、 $k$ が1ならば $i$ でも $k$ はそのままになります。 $k$ が0のとき、 $a+b$ の $i$ 桁目が'0'になるような計算をしたときに $k$ は1に変化し、'1'になるような計算をした場合は $k$ は0のままです。
$N$ の $i$ 桁目が'0'
$i-1$ の時点で、 $k$ が1ならば $i$ でも $k$ はそのままになります。
$k$ が0のとき、 $a+b$ の $i$ 桁目が'0'になるような計算をしたときに $k$ は0のままですが、'1'になるような計算をした場合はそもそも $N$ を超えてしまうので、遷移ができません。

ということで、 $a+b$ の $i$ 桁目が'0'になるか'1'になるかで、遷移が変わってくることがわかります。あとは、その他の遷移にかかわってくる条件をまとめて場合分けし、 $a+b$ の $i$ 桁目がどうなるかを調べれば、遷移が確定します。

3つの遷移に関わる条件について考え、 $a+b$ の $i$ 桁目がどうなるかを調べる

$(a,b,c,d)= \left\{ \begin{array}{} a,b: (a,b)のi桁目の組み合わせ、(0,0),(0,1),(1,1)の3通り\\ c: i-1桁目のjがどうであったか、0もしくは1 \\ d: i桁目のjがどうなるか、0もしくは1 \end{array} \right.$
として、場合分けをしていきます。

$(a,b,c,d)=(a+b)$ の $i$ 桁目
というように表記し、羅列していきます。 $×$ は、そのようになる可能性がないことを示します。
$(0,0,0,0) = 0$
$(0,0,0,1) = 1$
$(0,0,1,0) = ×$
$(0,0,1,1) = ×$
$(0,1,0,0) = 1$
$(0,1,0,1) = ×$
$(0,1,1,0) = ×$
$(0,1,1,1) = 0$
$(1,1,0,0) = ×$
$(1,1,0,1) = ×$
$(1,1,1,0) = 0$
$(1,1,1,1) = 1$
です。あとは、これらと $N$ の $i$ 桁目による遷移の条件をもとに、ひたすら羅列をしていくことで、答えを求めることができます。