天下一プログラマーコンテスト2015 予選B : C - 擬二等辺三角形

ややこしいが本番解けて良かった。
http://tenka1-2015-qualb.contest.atcoder.jp/tasks/tenka1_2015_qualB_c

問題

3辺の長さが以下を満たす(面積が正の)三角形を擬二等辺三角形と定義する。

• 各辺の長さは整数である。
• 各辺の長さは異なる。
• ある2辺の長さの差は1である。

3辺の長さの和がL以下であるような擬二等辺三角形となる3辺の和の長さの組み合わせ総数を求めよ。

解法

ある2辺が長さM,M+1と書けるとする。
残り1辺が2～2*Mかつ(M-1),M,(M+1)のいずれとも異なるならば、この三角形は擬二等辺三角形となる。
(M-1を除く理由は、(M-1),M,(M+1)を3辺とする三角形が2回カウントされるのを防ぐため)

よって辺の和が最長であるM+(M+1)+(2*M)=4*M+1≦LとなるMに対しては、(Mが1の時を除き)(2*M-4)個の擬二等辺三角形が考えられる。
4*M+1＞LとなるMについては、残り1辺の長さが2～(L-(2M+2))の間でかつ(M-1),M,(M+1)のいずれとも異なるものしか取れないのでこれらを数え上げていく。
各Mについて、2～(L-(2M+2))の間に(M-1),M,(M+1)が含まれるかどうかを愚直に確認するとTLEする。
以下の解では2～(L-(2M+2))の間に(M-1),M,(M+1)が含まれるかどうかがMを10000加算する間に変化しないかどうかチェックしつつ、Mを10000ずつ進めるという強引な方法を取った。

恐らく簡単な計算でそのような変化が生じるMも求められるはず。

ll L;
ll mo=1000000007;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L;
	
	ll ma=L/4;
	while(4*(ma+1)+1<=L) ma++;
	while(4*(ma)+1>L) ma--;
	ret = (ma%mo)*((ma-1)%mo)%mo*((mo+1)/2)%mo;
	if(ma>=4) (ret += ((ma-2)%mo)*((ma-3)%mo)%mo*((mo+1)/2)%mo)%=mo;
	
	for(ll xx=ma+1;xx+(xx+1)+2<=L;xx++) {
		ll a=2;
		ll b=L-(xx+xx+1);
		if(a>b) continue;
		ret += b-a+1+mo;
		if(a<=xx-1 && xx-1<=b) ret--;
		if(a<=xx && xx<=b) ret--;
		if(a<=xx+1 && xx+1<=b) ret--;
		ret %=mo;
		
		if(a<=xx-1 && xx-1<=b) {
			ll bn=L-(xx+9999+xx+9999+1);
			if(bn>=2 && (a<=xx+10000 && xx+10000<=bn)) {
				bn-=4;
				ll b1=L-(xx+1+xx+1+1)-4;
				(ret += (b1+bn)*9999/2)%=mo;
				ret %= mo;
				xx+=9999;
			}
		}
		else if((a<=xx-1 && xx-1<=b)==0) {
			ll bn=L-(xx+9999+xx+9999+1);
			if(bn>=2) {
				bn-=1;
				ll b1=L-(xx+1+xx+1+1)-1;
				(ret += (b1+bn)*9999/2)%=mo;
				xx+=9999;
			}
		}
	}
	
	cout<<ret<<endl;
}

まとめ

このあとのCF317でも三角形の数を求める問題が出てびっくり。