ARC066-D:Xor Sum - 思考の墓場

ある意味有名な(?)問題。解説と少し違ったので思うので書いてみる。

問題

考察

　とりあえず、xorと和の関係を表す式であるところの $a + b = a \ \mathrm {xor} \ b + 2 (a\ \mathrm{and} \ b) \cdots (*)$ を書いてみる。この式は、2つの自然数の足し算というのは、桁ごとの和(xor)と繰上がりに分解できるということを言っている。この式から $a + b \geq a\ \mathrm{xor} \ b$ がわかり、つまり問題文でいうところの $v \geq u$ がわかる。つまり、 $v \leq N$ ということだけ考えれば、 $N$ 以下ということは自動的に満たされる。
　 $v \leq N$ を固定したときに、条件を満たす $u$ の数を数えたい。当然 $v$ をすべて試すわけにはいかないので、うまい方法を考える。(*)式を見ると、 $v = (a+b)$ と $a\ \mathrm{and}\ b$ の値を決めれば、 $u (= a\ \mathrm{xor}\ b)$ の値も決まることがわかる。そこで、 $v$ の値を決めたときに、 $a \ \mathrm{and}\ b$ としてあり得るものを数えることを考えてみる。これは $v$ の2進数表記の各桁が、0か1かを決めながら数えられそうである。そこで、 $v$ の上位の桁から決めていく桁dpを考えることにする。ところが、上から決めるにあたって、 $v$ の各桁の値を決めていくだけでは正しく数えることができない。それは、足し算に繰り上がりがあるからである。そこで、今の桁は下の桁からの繰上あがりを考慮するか？という情報を持つことにする。dp定義をまとめれば

$dp _ {i,j,k}$ : $a + b$ の値を上から $i$ 桁目まで決めたときの $a\ \mathrm{and}\ b$ の通り数。ここで、 $j$ は $a+b \lt N$ が確定しているかどうかのフラグ、 $k$ は $i-1$ 桁目からの繰り上がりを考慮しているかどうかのフラグ。

dpの遷移は難しくない(実装参照)。例えば $a+b$ の上から $i+1$ 桁目を $1$ にするときを考える。 $a\ \mathrm{and} \ b$ を1にしたい場合、上から $i$ 桁目に繰り上がりが生じるので、 $dp _ {i,j,1}$ からの遷移が行われることになる。 $a\ \mathrm{and} \ b$ を0にしたい場合、上から $i+1$ 桁目への繰り上がりを考慮するかどうかで、遷移を場合分けすることになる。答えは $N$ が2進数表記で $n$ 桁であったとして、 $dp _ {n,0,0} + dp _ {n,1,0}$ となる。

実装

atcoder.jp

この解法は思いつきやすいと思う。