TopCoder Open 2016 Round 2B Easy. TriangleTriples

問題

辺の長さが 1≦a≦A, 1≦b≦B, 1≦c≦C であるような三角形 (a,b,c) の個数は何個あるか。

解法

三角形の成立条件は

$$ a+b>c \quad \land \quad b+c>a \quad \land \quad c+a>b $$

である。なので、不成立条件は

$$ a+b\le c \quad \lor \quad b+c\le a \quad \lor \quad c+a \le b $$

となる。よく考えると、同時に 2 条件が成り立つことはないため、それぞれのケースを独立に考えて足せばいい。 これは、機械的に包除原理に放り込んでみたら気がついた。

ということで

$$ a+b \le c $$

となる (a,b,c) の数を数える問題を考えてみよう。これは次の領域に含まれる格子点の数に等しい。

大きな三角錐から小さな三角錐を引いてあげれば格子点の数が求まる。A,Bが小さすぎて小さな三角形が重なってしまったら、重複分をキャンセルするように三角錐を足してあげればいい。

gist.github.com

こういう数式系苦手なので、ひたすらそれっぽい式を立てて愚直解と比較していた。