Codeforces #386 Div2 G. New Roads

これも2000ptぐらいかな。
http://codeforces.com/contest/746/problem/G

問題

N頂点の根付き木のうち、以下の条件を満たすものを作れ。

• 深さは最大T
• 深さdの頂点はA[d]個ずつある
• 葉となる頂点はK個

解法

まずA[1]～A[T]がいずれも正であることを確認する。
次に、葉の数が最小となるケースと最大となるケースを考えよう。

• 最大となるケース：
  • 深さdの頂点は、すべて深さ(d-1)の単一の頂点につながる。この時(N-T)個葉頂点ができる。
• 最小となるケース：
  • 深さdの頂点は、できるだけ深さ(d-1)の異なる頂点につなげる。すると深さ(d-1)の頂点はmax(0,A[d-1]-A[d])個だけ葉ができる

Kが上記２値の間なら条件を満たす木が作れる。
また、上記の考えで１本ずつ辺を増減することもできるので、問題の木は容易に作成できる。

int N;
ll A[101010];
ll S[101010];

ll O[101010];
ll ret=0;

ll mi[101010],ma[101010];
int nex[101010],nex2[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>A[0];
	FOR(i,N-1) {
		cin>>s>>A[i+1];
		O[i+1]=(s[0]=='+') ? 1 : -1;
	}
	FOR(i,N) S[i+1]=S[i]+A[i];
	nex[N]=N;
	nex[N-1]=N;
	for(i=N-2;i>=0;i--) {
		if(O[i+1]==-1) nex[i]=i+1;
		else nex[i]=nex[i+1];
	}
	
	if(N==1) return _P("%lld\n",A[0]);
	if(N==2) return _P("%lld\n",A[0]+O[1]*A[1]);
	mi[N-1]=ma[N-1]=A[N-1];
	for(i=N-2;i>=0;i--) {
		if(O[i+1]==1) {
			ma[i]=A[i]+ma[i+1];
			mi[i]=A[i]+mi[i+1];
		}
		else {
			ma[i]=max(A[i]-A[i+1]+ma[i+2],A[i]-A[i+1]-mi[i+2]);
			ma[i]=max(ma[i],A[i]-mi[i+1]);
			mi[i]=min(A[i]-A[i+1]-ma[i+2],A[i]-A[i+1]+mi[i+2]);
			mi[i]=min(mi[i],A[i]-ma[i+1]);
			if(nex[i+1]<N) {
				mi[i]=min(mi[i],A[i]-(S[nex[i+1]]-S[i+1])-mi[nex[i+1]]);
			}
		}
		
		//_P("%d %lld %lld\n",i,ma[i],mi[i]);
	}
	cout<<ma[0]<<endl;
	
}

まとめ

今回配点が謎だったな…。