ABC138-F:Coincidence - 思考の墓場

経験不足だった。

問題

解法

考察

　 $y$ を $x$ で割った余りが $x \ \rm{xor}\ y$ に等しいという条件が謎なので，もうすこしわかりやすい条件に言い換えることを目指そう。まず， $x \ \rm{xor}\ y$ がある自然数を $x$ で割った余りであるということから， $x \ \rm{xor}\ y \lt x$ が成り立つ。この不等式が成り立つためには， $y$ の2進法表記としての桁数は， $x$ のそれ以下で必要がある。さらに， $x\leq y$ であるから，結局 $y$ と $x$ の桁数は等しくなければいけない。 $x\leq y$ で両者の2進法表記で桁数が等しいとき， $y\lt 2x$ が言える( $2$ 倍することは桁を1つ増やすことに相当すると考えると明らか)。つまり， $y$ を $x$ で割ったときの商として考えられるものは $1$ しかない。よって，以下の等式を満たすような $x,y$ の組を数えればよい。

$y = x + (x \ \rm{xor} \ y)$

この条件から $x,y$ の各桁について何が言えるかを考える。 $x$ の $i$ 桁目が $1$ で $y$ の $i$ 桁目が $0$ であるとすると，左辺の足し算において繰り上がりが起き，辻褄が合わなくなる( $i+1$ 桁目がどうなるかを確認してみるとよい)。逆にそれ以外のパターンでは各桁が他の桁に影響を与えずに，条件が満たされることがわかる。つまり， $y$ と $x$ の桁数が等しく， $y,x$ の $i$ 桁目を $y_i,x_i$ としたとき， $(y_i,x_i) = (1,1),(1,0),(0,0)$ が満たされているようなものを数えればよいことがわかった。このとき， $x\leq y$ が自動的に保障されるので，以後 $x$ と $y$ の大小は気にしなくてよい。
　厄介なのは $L\leq x \leq y \leq R$ という条件だろう。ここは慣れていないと難しいと思うが，桁dpの考え方を応用する。つまり

$dp_{i,j,k}$ : $i$ 桁目まで見たときに， $y$ が $R$ より小さいことが確定しているかどうか( $j)$ ， $x$ が $L$ より大きいことが確定しているかどうか $(k)$ ，を決めたときの条件を満たす $(y,x)$ の組の場合の数

としてdpを行う。

dpの詳細と実装

　bool値を2つ状態としてもつので遷移がややこしく，あまり雑にやると実装が破滅する。落ちついて，「今の状態を固定したときに，何を決めれば次の状態が決まるか」を表にしてみよう。 $y$ と $x$ の各桁の関係は重要だが， $y$ の $i$ 桁目を決めたときに $y$ について次にどのような状態になるかは $x$ の情報は関係がない。よって， $y$ と $x$ について別々に表が作れる。
　今 $i$ 桁目までの答えがわかっていて， $i-1$ 桁目の答えを知りたいということにしよう。 $R$ の $i$ 桁目は $R$ と同じで， $i-1$ 桁以下はすべて0である数を $R_i$ とする。このとき，dpテーブルの $j$ という添え字は，「今は $y\lt R_i$ であるか？」ということを意味している。ここから $i-1$ 桁目での状態を決定するには， $R$ の $i-1$ 桁目が何であるかということと， $y$ の $i-1$ 桁目を何にするかということを決めればよい。これらの関係を表にすると以下のようになる。

$y$ の $i-1$ 桁目	$R$ の $i-1$ 桁目	$i$ 桁目での状態	$i-1$ 桁目での状態
$1$	$0$	$y \lt R_i$	$y' \lt R_{i-1}$
$1$	$0$	$y = R_i$	なし
$1$	$1$	$y \lt R_i$	$y' \lt R_{i-1}$
$1$	$1$	$y = R_i$	$y' = R_{i-1}$
$0$	$0$	$y \lt R_i$	$y' \lt R_{i-1}$
$0$	$0$	$y = R_i$	$y' = R_{i-1}$
$0$	$1$	$y \lt R_i$	$y' \lt R_{i-1}$
$0$	$1$	$y = R_i$	$y' \lt R_{i-1}$

この表を作ってしまえば， $i$ 桁目の状態と $i-1$ 桁目を何にするかをfor文で回し，表を見ながら次の状態を決めるのことができて，実装が簡潔になると(個人的には)思っている。 $x$ についても同様の表を示しておく。

$x$ の $i-1$ 桁目	$L$ の $i-1$ 桁目	$i$ 桁目での状態	$i-1$ 桁目での状態
$1$	$0$	$L_i \lt x$	$L_{i-1} \lt x'$
$1$	$0$	$L_i = x$	$L_{i-1} \lt x'$
$1$	$1$	$L_i \lt x$	$L_{i-1} \lt x'$
$1$	$1$	$L_i = x$	$L_{i-1} = x'$
$0$	$0$	$L_i \lt x$	$L_{i-1} \lt x'$
$0$	$0$	$L_i = x$	$L_{i-1} = x'$
$0$	$1$	$L_i \lt x$	$L_{i-1} \lt x'$
$0$	$1$	$L_i = x$	なし

$y,x$ の桁数が等しいという条件をどう組み込むかについて述べるのを忘れていた。最上位の桁として選ぶことができるのは，Rの最上位の桁から $L$ の最上位の桁までである。従って，該当する桁では $dp_{i,j,k}$ に適切に $j,k$ を選んで $1$ を足しておけばよい(詳細は実装を参照)。これでdpの遷移が完成した。

実装

Submission #7021885 - AtCoder Beginner Contest 138

　次の状態はだいたいは不等号なので，デフォルトで不等号にしておいて，特定の場合だけ変えるという実装がわかりやすいと思う。
　ところでmodintは便利ですね。