UVa 11401 : Triangle Counting

問題リンク : http://uva.onlinejudge.org/external/114/11401.pdf

問題概要 :
3以上の整数 n が与えられたとき、
長さが1からnまでの棒がそれぞれ1本ずつあるものとして
それらのうち3本を選んで作れる三角形の個数を出力せよ
n が3未満ならばプログラムを終了せよ

解法 :
三角形の成立条件は、
三角形を構成する三辺の長さa,b,cが以下の３つの不等式を満たすことである ( wikipedia より
* a < b + c
* b < a + c
* c < a + b
最も長い辺を c とすると、
c < a + b さえ成り立てば当然他のa,bの不等式も成り立つ ( c だけで既にa,bより長いので )
これより、最も長い辺を決めてそれ未満の長さの棒２本の長さの和が最も長い辺の長さより長くなるようなものの個数を選べばよい
これについて、次の例で考えてみる
n = 8
1 2 3 4 5 6 7 8
まず、8を最長のものとしそれ未満の棒を2本選んでみる
7 と [2,7)
6 と [3,6)
5 と [4,5)
という選び方がある
次に 7 を最長....
として数えれば良い
これは
初項が最長の辺の長さが奇数なら２、偶数なら１で
項数は ( 最長の辺の長さ - 2 ) / 2　で
末項は 初項 + 2 * ( 項数 - 1 ) の等差数列になっているのでそうして計算すると楽

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int MAX = 1000010;
long long answers[MAX];

int main(){
  REP(maximum_length,4,MAX) {
    long long a = (maximum_length&1)?2LL:1LL;
    long long n = ( maximum_length - 2 ) / 2;
    long long l = a + 2 * ( n - 1 );
    answers[maximum_length] = answers[maximum_length-1] + ( n * ( a + l ) ) / 2LL;
  }
  int n;
  while( scanf("%d",&n), n >= 3 ) printf("%lld\n",answers[n]);
  return 0;
}