読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Regular Contest 066: D - Xor Sum

寝坊したので不参加。

http://arc066.contest.atcoder.jp/tasks/arc066_b

関係あるかどうか微妙なのだが、この問題と問題設定が似ている問題がCodeforcesにある。Codeforcesの方の問題はcarry型の桁DPで"殴れる"(想定解は異なるものである)。

http://codeforces.com/contest/634/problem/B

解法

borrow型の桁DPの典型問題。

$a + b = u$, $a \oplus b = v$ となる$(a,b)$が複数あるのが厄介なので、$(a \;and\; b)=a$, $(a\; or\; b) = b$ という制約を付けておく。こうすることで$(a,b)$と$(u,v)$が一対一に対応するようになる。

$a \oplus b \le a + b$ なので、意識する条件は $a+b \le N$ のみである。よって、$N-a-b \ge 0$となる$a,b$は何通りあるか、という問題であることが分かった。


(減算器を十分に理解している方は、この項を読み飛ばしていただいて構いません)

borrow型の桁DPの考え方は筆算である。ただ、もう少し機械的っぽい感じにしたいので、減算器と同じであると言うことにする。回路的なのが好きじゃないのであれば筆算でいいです。減算器ってのは下図みたいなの。

f:id:pekempey:20161220164440p:plain

$S_i$は$N_i-A_i-B_i-C_i \bmod 2$、$C_{i+1}$は$N_i-A_i-B_i-C_i$のborrow(桁借り)。減算の入力が3つあるため、$C'$が取りうる値は$C'=0,1,2$である。そのためディジタルっぽくはない。

これをどう使うのかというと、下図のように繋げればいい。これでNビットの減算ができる。

f:id:pekempey:20161220164505p:plain

iビット目の出力は、i-1ビット目の出力とA[i],B[i],N[i]にのみ依存していることが分かるだろう。つまり、これはDPに使える。


$N-a-b \ge 0$を60bitくらいの減算器に突っ込んで、最終的なborrowが0になるものを数えればいい。なぜborrowが0ならOKなのかというと、もし61ビット目へのborrowが存在すると、永遠にborrowが伝搬されていき$N-a-b < 0$になるためである。ここまで分かればコードを書くのは難しくない。

carry型の桁DPというのは、全加算器をイメージすればOK。

変更履歴

2016/12/21: 「iビット目の出力は、i-1ビット目の出力と…」の辺りの表現が理解しづらいものであったため、修正しました。