AtCoder Grand Contest 015: D - A or...or B Problem

,

http://agc015.contest.atcoder.jp/tasks/agc015_d

やればできそうだけどしんどい感じの問題。考察をあまりせずに書き始めたら時間が溶けるだけに終わった。

solution

丁寧に場合分けして、MSBを取る操作を$O(1)$見做せば$O(1)$で求まる。

$A \lt B$としてよい。 $A, B$のMSBが同じなら両方からそれを除去してよい。これは再帰的にできて、$B$のMSBを$2^r$とすると$A \lt 2^r$であるようにできる。 生成される整数を$2^r$未満かどうかで分ける。

  • $2^r$未満であれば$B$は忘れて$[A, 2^r)$に制限してよい。 $[A, 2^r)$の範囲は自明に作れて、bit和を取って小さくなるので$A$未満は作れない。 よって$2^r - A$個。
  • $2^r$以上とする。 $B - 2^r$のMSBを$2^k$とする。 $B$により$2^r + 2^i$ for $i \lt k$の形の整数は全て作れ、$2^{k+1}$を含むようなものは作れない。よって$[2^r, B]$の範囲(のみ)から生成されるのは$[2^r, 2^r + 2^{k+1})$。 $[A, 2^r)$の範囲を考えた場合はこれに$2^r$を足すことで$[2^r + A, 2^{r+1})$の範囲が作れる。
    • $2^r + A \le 2^r + 2^{k+1}$の場合はこれらを合わせて$[2^r, 2^{r+1})$が全て作れて終わり。
    • そうでないとき$[2^r, 2^r + 2^{k+1})$と$[2^r + A, 2^{r+1})$からその間$[2^r + 2^{k+1}, 2^r+A)$に入る整数が作れるかどうかであるが、作れない。 $l \in [2^r, 2^r + 2^{k+1})$と$r \in [2^r + A, 2^{r+1})$の和$l + r \ge r$なので$l + r \in [2^r + A, 2^{r+1})$となるため。

implementation

#include <cstdio>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;

const int bit_size = 60;
int msb(ll x) {
    repeat_reverse (i, bit_size) {
        ll y = 1ll << i;
        if (y & x) return i;
    }
    return -1;
}
ll solve(ll a, ll b) {
    // drop unnecessarily bits
    while (true) {
        int r = msb(b);
        if (r == -1) break;
        ll x = 1ll << r;
        if ((a & x) and (b & x)) {
            a ^= x;
            b ^= x;
        } else {
            break;
        }
    }
    // trivial case
    if (b == 0) return 1;
    assert (a < b);
    // prepare
    int r = msb(b);
    ll x = 1ll << r;
    assert (     b & x);
    assert (not (a & x));
    ll result = 0;
    // the msb is true
    if (b == x) {
        if (a == 0) {
            result += x - a;
        } else {
            result += x - a + 1;
        }
    } else {
        int k = msb(b ^ x);
        assert (k != -1);
        if (a >= (1ll << (k+1))) {
            result += 1ll << (k+1);
            result += x - a;
        } else {
            result += x;
        }
    }
    // the msb is false
    result += x - a;
    return result;
}

int main() {
    ll a, b; scanf("%lld%lld", &a, &b);
    ll result = solve(a, b);
    printf("%lld\n", result);
    return 0;
}