SRM 546 div1 easy KleofasTail

問題

問題概要

xが偶数のとき　x / 2
xが奇数のとき x -= 1
ができる. [A, B]の数で上の操作を繰り返してKになるものの総数を求めよ.

解法

まず, 問題では小さくなる操作が与えられているが, 求めたいのはKになるかなので, Kから[A, B]の区間にいけるかを求めたほうがよさそうだということがわかる. 逆の操作の場合問題概要で示した操作は,
xが偶数のとき x = 2 (x <<= 1) または x += 1
xが奇数のとき　x = 2 (x <<= 1)
x(偶数)を2で割れば偶奇どちらもあり得るが, x(奇数)から1を引くときは偶数になるので, 逆の操作は上のようになる.
よって、Kから大きくしていくことを考えると, Kに対して2倍(K<<=1)と+1を繰り返して[A, B]の中に入るものの数をカウントすればよいことになる.
カウント方法はdfsで全探索をすれば簡単ではあるが, 今回は数が大きいので無理. そこでKから作られる数の特性を利用する.
Kが偶数のとき (Kのbit)(任意のbit)　または (K+1のbit)(任意のbit)
Kが奇数のとき (Kのbit)(任意のbit)
という数が作られることになるので, それを任意のbitの桁数ごとにいくつ範囲に入るかをカウントしてりけばいい. 任意のbitになるのは, +1と2倍(シフト)があれば作れるからだ. 例えば(Kのbit101)を作りたいなら, Kをシフトして+1して, さらに2回シフトして+1すれば作れる.
[A, B]の範囲に入るものをいきなり計算してもいいが, [0, A - 1], [0, B]をそれぞれ計算して,
[0, B] - [0, A - 1]で計算すれば実装が楽になる.

ミス

ぜんぜんわからなかった. Kから大きくしていく逆の操作でやるんだろうなということはわかっていたが, それ以上思いつかなった. ただ, Xが偶数の時に2で割ることは右へシフトさせたことと同じで, 奇数の時に-1をすることは最下位bitを0にすることと同じ. このような感覚を持ち, bitで考えようとすれば答えにたどり着けたかも. Kから全探索すればわかるわけだし, それをどう計算量を落とすかか.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

class KleofasTail
{
public:
    //逆からたどる
    ll solve(ll k, ll x){ //[0, x)までの数で、途中で　k になるやつの数
        ll ret = 0;
        if(k % 2 == 0){//kが最下位bitが 0
            //そのままシフト
            for (ll i = 1; i * k < x; i *= 2){//[ k*2^i, k*2^(i+1) )　までが何個あるかをカウント
                ret += min(i, x - k * i); //x以上の部分をカウントしないようにする
            }
            //+1をした後にシフト
            for (ll i = 1; i * (k  + 1) < x; i *= 2){//[ k*2^i, k*2^(i+1) )　までが何個あるかをカウント
                ret += min(i, x - (k + 1) * i); //x以上の部分をカウントしないようにする
            }
        }else{
            //そんままシフト
            for (ll i = 1; i * k < x; i *= 2){//[ k*2^i, k*2^(i+1) )　までが何個あるかをカウント
                ret += min(i, x - k * i); //x以上の部分をカウントしないようにする
            }
        }
        return ret;
    }

    long long countGoodSequences(long long K, long long A, long long B){
        if(K == 0) return B - A + 1; // K==0 のときは上位bitが何も決まっていないじょうたいなので任意の数字を作ることができる.
        return solve(K, B + 1) - solve(K, A);
    }
};

int main(void){
    KleofasTail kt;
    // printf("%lld\n", kt.countGoodSequences(3, 4, 8)); // 2
    printf("%lld\n", kt.countGoodSequences(0, 0, 2));//3
    return 0;
}