問題
http://community.topcoder.com/stat?c=problem_statement&pm=11463
4と７からなる数字をluckynumberと呼ぶ。
数字の範囲a<=x<=bであるa,bが最初に与えられ、JohnとBrusでゲームを行う。
最初はJohnのターンであり、jLenの長さだけ連続した数字を選ぶ。Johnはできるだけ最終的にluckynumberが多く含むようにしたい。
次はBrusのターンであり、Johnが選んだ数字からbLenの長さだけ連続した数字を選ぶ。Brusはできるだけluckynumberを少なく含むようにしたい。
このとき、Johnが得ることのできるもっとも多いluckynumberの数を求める。
解き方
数の範囲が10^10なので全探索では解けない。
ここで、luckynumberに着目するとその数は2^11になるので、luckynumberをからめて考えることができれば解けるようになる。
次に、luckynumberとからめてどうすればJohnができるだけ多くの数字を得られて、Brusができるだけ少ない選び方ができるかを考える。
Johnについてはluckynumber-blen+1から初めて数字を取り始めれば最も多く数字をとることができる。
Brusはluckynumber+1から初めて数字を取り始めれば最も少なく数字をとることができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#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()
long long blen;
vector<long long> luckynum;
int n;
class TheLuckyGameDivOne {
public:
void getnum(long long a,long long b,long long x){
if(x<=b){
if(a<=x)luckynum.push_back(x);
getnum(a,b,x*10+4);
getnum(a,b,x*10+7);
}
}
int countnum(long long x){
int low=-1,high=n;
while(high-low>1){
int mid=(low+high)/2;
if(luckynum[mid]>=x)high=mid;
else low=mid;
}
return high;
}
int f(long long x){
return countnum(x+blen)-countnum(x);
}
int bestBrus(long long start,long long end){
int ret=f(start);
FORE(i,0,n){
long long cur=luckynum[i]+1;
if(start<=cur && cur+blen-1<=end){
ret=min(ret,f(cur));
}
}
return ret;
}
int find(long long a, long long b, long long jLen, long long bLen_) {
blen=bLen_;
luckynum.clear();
getnum(a,b,0);
sort(all(luckynum));
n=luckynum.size();
int ret=bestBrus(a,a+jLen-1);
FORE(i,0,n){
long long cur=luckynum[i]-blen+1;
if(a<=cur && cur+jLen-1<=b)ret=max(ret,bestBrus(cur,cur+jLen-1));
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#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()
long long blen;
vector<long long> luckynum;
int n;
class TheLuckyGameDivOne {
public:
void getnum(long long a,long long b,long long x){
if(x<=b){
if(a<=x)luckynum.push_back(x);
getnum(a,b,x*10+4);
getnum(a,b,x*10+7);
}
}
int countnum(long long x){
int low=-1,high=n;
while(high-low>1){
int mid=(low+high)/2;
if(luckynum[mid]>=x)high=mid;
else low=mid;
}
return high;
}
int f(long long x){
return countnum(x+blen)-countnum(x);
}
int bestBrus(long long start,long long end){
int ret=f(start);
FORE(i,0,n){
long long cur=luckynum[i]+1;
if(start<=cur && cur+blen-1<=end){
ret=min(ret,f(cur));
}
}
return ret;
}
int find(long long a, long long b, long long jLen, long long bLen_) {
blen=bLen_;
luckynum.clear();
getnum(a,b,0);
sort(all(luckynum));
n=luckynum.size();
int ret=bestBrus(a,a+jLen-1);
FORE(i,0,n){
long long cur=luckynum[i]-blen+1;
if(a<=cur && cur+jLen-1<=b)ret=max(ret,bestBrus(cur,cur+jLen-1));
}
return ret;
}
};