NOMURA プログラミングコンテスト 2020 : C - Folia

C,Dまではすんなりいったんだけどな。
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c

問題

深さNの二分木を考える。
D[i]を、深さiにおける葉の数とする。
条件を満たす二分木が作れるか、作れるなら最大頂点数を示せ。

解法

深い方から順に、各深さで取りえる頂点数の範囲を考えよう。
深さ(i+1)での範囲が[L[i+1],R[i+1]]の時、深さiでは葉ではない頂点数はその半分以上あればいいので、
L[i]=A[i]+ceil(L[i+1]/2)
R[i]=A[i]+R[i+1]
となる。

最終的にL[0]=1なら解があるので、あとは先ほどの[L[i],R[i]]からはみ出ない範囲で各深さの頂点数V[i]を最大化する。
具体的には以下の通り遷移する。
V[0]=1
V[i+1]=min(R[i+1],(V[i]-A[i])*2)

int N;
int A[101010];
ll L[101010],R[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) cin>>A[i];
	L[N]=R[N]=A[N];
	for(i=N-1;i>=0;i--) {
		L[i]=A[i]+(L[i+1]+1)/2;
		R[i]=A[i]+R[i+1];
	}
	if(L[0]>1) return _P("-1\n");
	ll cur=1;
	ll ret=0;
	FOR(i,N+1) {
		ret+=cur;
		cur-=A[i];
		cur=min(cur*2,R[i+1]);
	}
	cout<<ret<<endl;
}

まとめ

ここらへんは順調だったのにね。