kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2016 Round2B Easy TriangleTriples

TCOらしからぬ問題?
https://community.topcoder.com/stat?c=problem_statement&pm=14286

問題

正整数A,B,Cが与えられる。
1≦a≦A、1≦b≦B、1≦c≦Cを満たす整数(a,b,c)の組のうち、3辺がこの長さを持つ正の面積の三角形が存在できるものは何通りあるか。

解法

(a,b,c)の組み合わせA*B*C通りから、三角形が作れないものを除こう。
三角形を作るには、a+b>c、b+c>a、c+a>bのすべてを満たさなければならない。
逆にa+b≦c、b+c≦a、c+a≦bのいずれか1つでも満たしたら三角形を作れない。
また、この3条件は3つ同時に満たすことはなく、満たせるのは1つである。
そこで上記条件に相当するものをそれぞれ取り除こう。

これには、立体図形を考えるとよい。
(1,1,1)-(A,B,C)を対角線とする直方体から、上記3条件に相当する部分を取り除き、その格子点を数えることになる。
例えばb+c≦aなら、(A,1,1),(2,1,1),(A,A-1,1),(A,1,A-1)を結んだ三角錐を取り除くことになる。
その際、三角錐と直方体の共通部分だけを取り除かなければならない。
これは包除原理の要領で三角錐の足し引きをすればよい。

ll mo=1000000007;

class TriangleTriples {
	public:
	ll tri(ll a) {
		if(a<1) return 0;
		return a*(a+1)%mo*(a-1)%mo*((mo+1)/6)%mo;
	}
	
	int count(int A, int B, int C) {
		if(A>B) swap(A,B);
		if(B>C) swap(B,C);
		if(A>B) swap(A,B);
		
		ll ret=1LL*A*B%mo*C%mo;
		ret -= tri(A);
		ret -= tri(B);
		ret += tri(B-A);
		ret -= tri(C);
		ret += tri(C-A);
		ret += tri(C-B);
		ret -= tri(C-A-B);
		
		return (ret%mo+mo)%mo;
		
	}
}

まとめ

本番は式をグリグリこねまわしてコーナーケースで落とした。