yukicoder : No.1555 Constructed Balancing Sequence

こういうの解ける気しないな。
https://yukicoder.me/problems/no/1555

問題

長さNの整数列Aがバランスが良いとは、A[i]≦sum(A[0...(i-1)])であることを意味する。

整数N,Kと整数列Aが与えられる。
以下の条件を満たす長さBの整数列は何通りあるか。

• B[i]は-K以上K以下である。
• B[i]≦C[i]が成り立つバランスの良い長さ整数列Cのうち、辞書順最小のものがAとなる。

解法

ほぼEditorialそのままですが。

まず-K≦B[i]≦A[i]は条件より明らか。
次に、後者の条件を考える。
C(i)を、i要素目で初めてAより辞書順で小さいことが確定するバランスの良い整数列のうち最大のものとする。
すなわち

• j＜iならC(i)[j] = A[j]
• j=iならC(i)[j] = A[j]-1
• j＞iなら最大値、すなわちC(i)[j] = sum(C(i)[0]+...+C(i)[j-1])

Iを、i＜jにおいてA[j]≦C(i)[j]であるiの集合とする。
求めるのは、i∈IにおいてB[i]=A[i]であることである。

Iさえ求めてしまえば、i∉Iにおいて(A[i]+K+1)の積を取ったものが解となる。
Iは、C(i)[j]はjが増えると倍々に増えるので、各iに対しjを30個位たどれば判定できる。

int N,K;
int A[101010];
ll S[101010];
const ll mo=998244353;
int P[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		P[i+1]=P[i]+(A[i]>0);
	}
	ll ret=1;
	FOR(i,N) {
		ll s=S[i+1]-1;
		int fix=0;
		if(s>0) {
			fix=1;
			for(j=i+1;j<N&&fix;j++) {
				if(A[j]>s) fix=0;
				if(s>K) break;
				s*=2;
			}
		}
		else if(s==0) {
			fix=(P[N]-P[i+1])==0;
		}
		else if(s<0) {
			fix=1;
			for(j=i+1;j<N&&fix;j++) {
				if(A[j]>s) fix=0;
				s*=2;
			}
		}
		
		if(fix==0) ret=ret*(A[i]+K+1)%mo;
		
	}
	cout<<ret<<endl;
}

まとめ

実装はともかく、考察段階がしんどいな。