Codeforces ECR #026 : F. Prefix Sums

これも手間取った。
http://codeforces.com/contest/837/problem/F

問題

m要素の数列Xに対し、関数pを適用して得られる(m+1)要素の数列p(X)=Yをと定める。
ここで数列A^0が与えられる。Aにi回関数pを適用したものをA^iとする。
A^iの要素にK以上の値が現れるのは最小のiを求めよ。

なお、A^0は２つ以上の非ゼロ成分を持つ。

解法

非0成分を1個しか持っていない数列B^0[0]=1を考える。
この時B^i[i+k]の値はO(i^k)の値を取る。

まずA^0のゼロ成分のprefixをすべて取り除いたとする。
この数列の長さが4以上なら、A^iの末尾の値はO(i^3)以上で増加するので、iを10^6の数倍程度までシミュレーションすれば条件を満たすiにぶつかる。

そうでない場合、A^0の長さが2または3ならiを二分探索すればよい。
iがわかったとき、A^iの末尾の値はO(i)やO(i^2)程度の値となるが、これは計算で求めることができる。

int N;
ll K,A[202020],B[202020];

int ok(ll turn) {
	if(N==2) {
		ll tot=A[0];
		tot*=turn;
		if(tot/turn!=A[0]) return 1;
		return tot+A[1]>=K;
	}
	else if(N==3) {
		ll tot=0;
		if(A[0]) {
			tot = turn*(turn+1);
			if(tot/turn!=turn+1) return 1;
			tot /= 2;
			if(tot*A[0]/tot!=A[0]) return 1;
			tot*=A[0];
			if(tot>=K) return 1;
		}
		if(A[1]*turn/turn!=A[1]) return 1;
		if(A[1]*turn>=K) return 1;
		
		return tot+A[1]*turn+A[2]>=K;
	}
	else {
		assert(0);
		return 0;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int first=1;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]) first=0;
		B[i]=A[i];
		if(first&&A[i]==0) i--, N--;
		if(A[i]>=K) return _P("0\n");
	}
	
	
	FOR(i,2000000) {
		ll tot=0;
		FOR(j,N) {
			tot+=B[j];
			if(tot>=K) return _P("%d\n",i+1);
			B[j]=tot;
		}
	}
	
	ll ret=(1LL<<60)-1;
	for(i=59;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

Aが長いケースは早々に考慮できたが、逆に短いケースを見落として手間取った。