モラトリアムライフ

自由を求めて

yukicoderのNo.822 Bitwise ANDをACした

問題はこちらから

問題概要

$x$ & $y = N$ かつ $y - x \leq K$ を満たす整数の組 $(x, y)$ の個数を求めよ (無限個の場合はINFと出力)

制約

$0 \leq N \leq 10^{5}$ かつ $0 \leq K \leq 300$

考察

まず, 無限個になる場合を判定したい. 大きくなるほど, 差は多くなると考えられる.
$y$ の最上位ビットとして $N$ の最上位ビットよりも大きな $t$ ビットが立っているときの差の最小値は $y$ をできるだけ増やして, $x$ をできるだけ小さくしたい. したがって, $i =$ 1 ~ ( $t - 1$ ) ビット目を $K$ の $i$ ビットが立っているなら, $x$ , $y$ ともに1, 立っていないなら $x$ は1, $y$ は 0 とすればよい. この差の最小値は $2^{t-1}$ | $N- (2^{t-1} - 1) = N+1$ だから, $K$ と $N+1$ の大きさを比べれば良い.

$K \geq N+1$ のとき

$x, y$ を上記の作り方をすれば無限個存在する.

$K$ < $N+1$ のとき

上記議論から, $t$ ビットが立っているような $t$ の数は高々有限個. したがって, 有限個の組しか存在しないまた, andの性質から $x, y$ はともに $N$ よりも大きく, かつ $N$ の最上位ビット以上のとこにビットがあってはならない. これを全探索すれば良い！

解答