SRM 546 DIV1 Easy - KleofasTail （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12049&rd=14738
整数が与えられる。
整数が偶数のときは２で割り、奇数であれば１を引くことができる。
整数の範囲とある数が与えられた時、
その整数の範囲内である数が存在する数が何通りあるか求める。
解き方
数が１０＾１８のため、範囲中の全ての数を全探索で求めることはできない。
そのため、法則がないか数を列挙してみる。
ここで状態遷移図を用いてみる。
１）ｋが偶数のとき
Ｋ←２Ｋ←２Ｋ＋１←４Ｋ＋２←８Ｋ＋４
←４Ｋ＋３
←４Ｋ←８Ｋ←１６Ｋ
←８Ｋ＋１
←４Ｋ＋１←８Ｋ＋２
←Ｋ＋１←２Ｋ＋２←４Ｋ＋４←８Ｋ＋８
←４Ｋ＋５
←２Ｋ＋３←４Ｋ＋６→４Ｋ＋７
２）ｋが奇数のとき
Ｋ←２Ｋ←２Ｋ＋１←４Ｋ＋２←８Ｋ＋４
←４Ｋ＋３
←４Ｋ←８Ｋ←１６Ｋ
←８Ｋ＋１
←４Ｋ＋１←８Ｋ＋２
つまり、以下の法則が導ける。
ｋが偶数のときは
Ｋ～Ｋ＋１，２Ｋ～２Ｋ＋３、４Ｋ～４Ｋ＋７
ｋが奇数のときは
Ｋ、２Ｋ～２Ｋ＋１、４Ｋ～４Ｋ＋３
最小はＫの倍数、最大はＫもしくはＫ＋１から始まり２倍＋１となる。
コード
class KleofasTail {
public:
long long calc(long long K,long long B){
long long ans=0,low=K,high=K;
if(K%2==0)high++;
while(low<=B){
ans+=min(high,B)-low+1;
low=2*low;
high=2*high+1;
}
return ans;
}
long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;
return calc(K,B)-calc(K,A-1);
}
};
public:
long long calc(long long K,long long B){
long long ans=0,low=K,high=K;
if(K%2==0)high++;
while(low<=B){
ans+=min(high,B)-low+1;
low=2*low;
high=2*high+1;
}
return ans;
}
long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;
return calc(K,B)-calc(K,A-1);
}
};
using namespace std;
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class KleofasTail {
public:
long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;
long long ret=0;
long long e= K%2==1 ? 1 : 2;
long long cur=K;
while(cur<=B){
long long minx=max(cur,A);
long long maxx=min(cur+e-1,B);
ret+=max(0LL,maxx-minx+1);
cur*=2,e*=2;
}
return ret;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class KleofasTail {
public:
long long countGoodSequences(long long K, long long A, long long B) {
if(K==0)return B-A+1;
long long ret=0;
long long e= K%2==1 ? 1 : 2;
long long cur=K;
while(cur<=B){
long long minx=max(cur,A);
long long maxx=min(cur+e-1,B);
ret+=max(0LL,maxx-minx+1);
cur*=2,e*=2;
}
return ret;
}
};
