【AGC015-D】A or ... or B problem を解いた

【自分の解法】

自明に$\ A\leq x\leq B\ $を満たす任意の$\ x \in \mathbb{N}\ $は構築できる。

ここで，伝家の宝刀†$\rm{dp}$†を用いて実験すると，どうやら$ A\leq x\leq l,\ r\leq x\leq f(A, B)\ $を満たす任意の$\ x \in \mathbb{N}\ $と構築できる$\ x \in \mathbb{N}\ $の集合が一致するような$l,\ r\ (l \leq r)$が存在するらしい。(ただし，$\ f(A,\ B)\ $は構築できる最大の整数)

このとき，求める答えは$$f(A,\ B) - A + 1 - max(r - l - 1, 0)$$である。

よって，この問題に解答する為には，$f(A,\ B),\ l,\ r$を求めればよい。

【$f(A, \ B)$を求める】

自明に$f(A, \ B) = A or ... or B$であるので，桁ごとに考える。

2進数で見て，$A,\ B$が上からみて下から$k$桁目まで一致しているとき，$k - 1$桁以下の桁は全て$1$にすることが可能なので，求める答えは，

$$ 2^k - 1 + \displaystyle \sum_{p = k}^{10^{1000}} (2^p\  \rm{and} \  B)$$

【$l,\ r$を求める】

まず，$A\leq \displaystyle \sum_{p = k}^{10^{1000}} (2^p\ \rm{and} \ B) \leq B$を満たすもののうち，最大のものを$v$とする。また，$B \leq l \leq r$であるので，

$$l = f(v, B),\ r = v\  \rm{or} \  A$$である。

これより，$B$の桁数を$N$として，時間計算量$\rm{O}(N)$でこの問題を解くことができた。