Codeforces #728 Div1 : C2. Converging Array (Hard Version)

Hardは本番中に解けず。
https://codeforces.com/contest/1540/problem/C2

問題

N要素の数列Aと(N-1)要素の数列Bに対し、以下の処理を考える。

• 0≦i＜N-1を選び、A[i]=min(A[i], (A[i]+A[i+1]-B[i])/2), A[i+1]=max(A[i], (A[i]+A[i+1]+B[i])/2)を同時に行う。A[i]は整数でなくなることもある。

この処理を繰り返すと、いずれAは収束する。F(A,B)は、収束したときのA[0]の値とする。

N要素の数列Cが与えられる。
Aの各要素を、0≦A[i]≦C[i]の範囲の整数値とするとき、以下のクエリに答えよ。

• 整数値Xが与えられる。F(A,B)≦XとなるAは何通りあるか答えよ。

解法

収束したときのAをFと表現すると、以下の性質がわかる。

• C[i+1]-C[i] = max(B[i],A[i+1]-A[i])
• sum(C)=sum(A)

AやBのprefix sumをAP,BPとすると、F[0]=min*1となる。

これを踏まえて。まずBが与えられた時点で、A={0,0,...}のケースとA=Cのケースを考えるとF[0]の範囲はmax(C)程度の区間に限定される。
これらの範囲内の値Xに対し、F[0]≦Xとなるケースを数え上げよう。
これは(AP[i]-BP[i])-X*(i+1)≧0をキープできているか、AP[i]が各値になる組み合わせを累積和を取りながら数えて行けばよい。

int N;
int C[101];
int B[101],S[101];
int Q;
int X;
const ll mo=1000000007;
ll from[10101];
ll to[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll allpat=1;
	FOR(i,N) {
		cin>>C[i];
		allpat=allpat*(C[i]+1)%mo;
	}
	FOR(i,N-1) {
		cin>>x;
		B[i+1]=B[i]+x;
		S[i+1]=S[i]+B[i+1];
	}
	
	int lower=1LL<<30;
	for(i=1;i<=N;i++) {
		lower=min(lower,(100*i-S[i-1])/i-3);
	}
	
	
	map<int,ll> memo;
	for(X=lower-110;X<=lower+5;X++) {
		ZERO(from);
		from[0]=1;
		FOR(i,N) {
			ZERO(to);
			y=C[i];
			FOR(x,100*i+1) {
				
				int border=x-S[i]-X*(i+1);
				if(border>=0) {
					(to[x]+=from[x])%=mo;
					(to[x+y+1]+=mo-from[x])%=mo;
				}
				else if(border<-y) {
					;
				}
				else {
					(to[x-border]+=from[x])%=mo;
					(to[x+y+1]+=mo-from[x])%=mo;
				}
			}
			for(x=1;x<=100*(i+1)+1;x++) {
				(to[x]+=to[x-1])%=mo;
			}
			
			swap(from,to);
		}
		ll ret=0;
		FOR(i,10100) ret+=from[i];
		memo[X]=ret%mo;
	}
	
	cin>>Q;
	while(Q--) {
		cin>>X;
		if(X>lower+5) {
			cout<<0<<endl;
		}
		else if(X<lower-110) {
			cout<<allpat<<endl;
		}
		else {
			cout<<memo[X]<<endl;
		}
	}
	
}

まとめ

割とややこしい。

*1:AP[i]-BP[i])/(i+1