Codeforces #317 Div1 A. Lengthening Sticks

Tシャツ付の回に限って過去最大級の惨敗。
http://codeforces.com/contest/571/problem/A

問題

長さがA,B,Cの3本の辺がある。
これらの辺を、合計で最大Lまで整数単位で長くすることができる。
その結果、3辺が面積が正の三角形を成せるような辺の伸ばし方の組み合わせを求めよ。

解法

3辺の伸ばし方の組み合わせは通りある。
ここから、三角形を成せないケースを引いていく。

三角形を成せないケースは、どこか1辺が他の2辺の長さの和以上の長さを持つ場合である。
例えばAを少し伸ばした(A+i)の辺が最長の場合、(B+C+j)≦(A+i)かつ(i+j≦L)となるi,jの組み合わせの数だけ三角形を成せないケースが生じる。
よってiごとにjの組み合わせ数を累積していけば題意を満たさないケースを数え上げることができる。

同様に、B,Cの辺が最長のケースも取り除けば答え。

ll A,B,C,L;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>L;
	
	for(i=0;i<=L;i++) {
		ll a=A+i;
		ll left = L-i;
		ret += (left+1)*(left+2)/2;
	}
	FOR(j,3) {
		for(i=0;i<=L;i++) {
			ll a=A+i;
			ll left = L-i;
			// B+b+C+c<=a
			ll x=min(left,a-B-C);
			if(x>=0) ret -= (x+1)*(x+2)/2;
		}
		if(j==0) swap(A,B);
		if(j==1) swap(A,C);
	}
	cout<<ret<<endl;
	
}

まとめ

直前に天下一コン予選で似た問題解いていたので、こちらは比較的早く解けた…かと思ったらかなり苦戦してしまった。