TopCoder SRM 510 Div1 Medium TheLuckyGameDivOne

Div1 Mediumだけど、Div2 Mediumの制限を厳しくした問題なので先に挑戦。
http://community.topcoder.com/stat?c=problem_statement&pm=11463

問題

各桁4か7だけで構成されている数はlucky numberである。

初期状態でa～bの整数が与えられる。
先手はこのうち連続するjLen個の整数を選択し、後手は先手が選択したjLen個の中からbLen個の整数を選択する。

後手は最終的に選んだ整数内のlucky numberの数を最小化しようとする。
先手は逆にlucky numberの数を最大化しようとする場合、bLen個の中に含まれるlucky numberの数を答えよ。

解法

a,bの範囲は1～10^10とかなり広い。
しかし、lucky numberの数はかなり少ない。
N桁のlucky numberは各桁4か7の2^N通りしかないので、10^10までには510個しかない。

よって、a～bの間からx～(x+bLen-1)のbLen個の数値を選ぶことを考えた場合、尺取法の要領でxを1からb-(bLen-1)まで動かしていくと、区間内のlucky numberの数が増減するのは区間にlucky numberが入るときと出るときで510*2個位しか変化しない。
よってlucky numberの数が変化するxを列挙しよう。

次に、a～bからy～(y+jLen-1)のyLen個の数値を選ぶことを考えるわけだが、こちらも尺取法の要領でy～(y+jLen-1)の区間に含まれるlucky numberの数が変化するxを列挙し、そのlucky numberの最小値を求めればよい。

下記コードでは、yについては尺取法をせず、xの前後からlucky numberの変化しそうなyの候補を総当たりで列挙している。
列挙したyが最大9000個程度、xが1000個程度なので、y～(y+jLen-1)に含まれるxに対応するlucky numberを列挙しても十分間に合う。

class TheLuckyGameDivOne {
	public:
	ll A,B,BL,JL;
	vector<ll> cand,key;
	vector<int> value;
	
	int N;
	void add(ll v) {
		if(v>B) return;
		if(v>=A) cand.push_back(v);
		add(v*10+4);
		add(v*10+7);
	}
	
	int lb(ll val) {
		return lower_bound(cand.begin(),cand.end(),val+BL)-lower_bound(cand.begin(),cand.end(),val);
	}
	int test(ll val) {
		if(val<A || val+JL-1>B) return -1;
		int s = upper_bound(key.begin(),key.end(),val) - key.begin()-1;
		int e = upper_bound(key.begin(),key.end(),val+JL-BL) - key.begin();
		int mi=value[s];
		for(;s<e;s++) mi=min(mi,value[s]);
		return mi;
		
	}
	int find(long long a, long long b, long long jLen, long long bLen) {
		int x,y;
		
		A=a,B=b,BL=bLen,JL=jLen;
		cand.clear();
		add(0);
		sort(cand.begin(),cand.end());
		
		N=cand.size();
		
		key.clear(); value.clear();
		key.push_back(a);
		key.push_back(b-(bLen-1));
		
		FOR(x,N) {
			if(cand[x]+1 >= a && cand[x]+bLen < b) key.push_back(cand[x]+1);
			if(cand[x]-bLen+1 >= a && cand[x] < b ) key.push_back(cand[x]-(bLen-1));
		}
		
		sort(key.begin(),key.end());
		key.erase(unique(key.begin(),key.end()),key.end());
		ITR(it,key) value.push_back(lb(*it));
		
		
		set<ll> key2;
		FOR(x,key.size()) {
			key2.insert(key[x]-1);
			key2.insert(key[x]);
			key2.insert(key[x]+1);
			key2.insert(key[x]-1-(jLen-1));
			key2.insert(key[x]-(jLen-1));
			key2.insert(key[x]+1-(jLen-1));
			key2.insert(key[x]-1+(jLen-1));
			key2.insert(key[x]+(jLen-1));
			key2.insert(key[x]+1+(jLen-1));
		}
		
		int ma=0;
		ITR(it,key2) ma=max(ma,test(*it));
		return ma;
	}
};

まとめ

どうせ桁DPだと思ったら違った…。