Codeforces 121 D. Lucky Segments

問題

lucky numberを、全ての桁が4か7であるような数とする。

n個の区間[ l[i],r[i] ]が与えられる。
一つの区間を、一回の操作で[l[i]+1,r[i]+1]または[l[i]-1,r[i]-1]に移動させることができる。

全体でk回の操作ができるとき、
全ての区間に含まれていて、かつlucky numberであるような数を最大で何個にできるか、求めよ。

制約条件

n≦10^5
l[i],r[i],k≦10^18

方針

lucky numberを全生成して尺取法や二分法を使う解法が思い浮かぶが、
lucky numberは全部で20万個ほどあり、TLEになる。

全部の区間がある区間[L,R]を含むのは、
この区間が一番小さい区間の大きさ以下であり、
全ての区間の左端の数がL以下かつ、右端の値がR以上であることが必要十分である。

全ての区間の左端をL以下にするコストと、右端をR以上にするコストは、独立に求めることができる。
これは尺取っぽくlucky[i]とlucky[i-1]に入っている左端をL以下にするコスト+今までの左端の数*(lucky[i]-lucky[i-1])を更新していくことで求められる。

全ての左端右端をcl[i]以上,cr[i]以下にするコストが前計算で求まったら、
普通の尺取を使って答えを求めればいい。

掛け算がlong longの範囲でオーバーフローするので、
オーバーフローしたらk+1に適宜置き換えるなどの工夫が少し必要。

ソースコード

int n,m;
ll k,l[100000],r[100000];
ll lucky[1000000];
ll cl[1000000],cr[1000000];
ll M(ll a,ll b){
	if(1.0*a*b>k+1)return k+1;
	return a*b;
}
void run()
{
	m=1;
	for(int i=0;lucky[i]*10+7<(ll)1e18;i++){
		lucky[m++]=lucky[i]*10+4;
		lucky[m++]=lucky[i]*10+7;
	}
	cin>>n>>k;
	ll width=(ll)2e18;
	rep(i,n){
		cin>>l[i]>>r[i];
		width=min(width,r[i]-l[i]);
	}
	sort(l,l+n);
	sort(r,r+n);
	
	int j=n-1;
	for(int i=m-2;i>=0;i--){
		cl[i]=cl[i+1]+M(n-j-1,lucky[i+1]-lucky[i]);
		while(j>=0&&lucky[i]<=l[j]){
			cl[i]+=l[j--]-lucky[i];
			cl[i]=min(cl[i],k+1);
		}
	}
	j=0;
	for(int i=1;i<m;i++){
		cr[i]=cr[i-1]+M(j,lucky[i]-lucky[i-1]);
		while(j<n&&lucky[i]>=r[j]){
			cr[i]+=lucky[i]-r[j++];
			cr[i]=min(cr[i],k+1);
		}
	}
	
	j=0;
	int ans=0;
	for(int i=1;i<m;i++){
		j=max(i,j);
		while(j<m&&lucky[j]-lucky[i]<=width&&cl[i]+cr[j]<=k)j++;
		ans=max(ans,j-i);
	}
	cout<<ans<<endl;
}