CodeIQ 三角形は何通り？ - 　ゆずねのあとりえ　~Atelier of Yuzune~

今日は以下の問題を解いてみました。

――――――――――――――――――――――――――――――――――――――――――
【問題】
入力nに対して
$1\leq a \leq b\leq c \leq n$ （ $a, b, c, n$ はすべて整数）を満たす $a, b, c$ の中で、
これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。

【入力】
標準入力から、整数 $n（1 \leq n \leq 1000000）$ が与えられます。

【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。
――――――――――――――――――――――――――――――――――――――――――

まずは何も考えずに $1\leq a \leq b\leq c \leq n$ となる組み合わせを全て調べてみます。

//CodeIQ 三角形は何通り？：愚直に全探索
#include<iostream>
using namespace std;

int64_t solve(const int n) {
	int64_t count = 0;
	for (int c = n;c >= 1;c--) {
		for (int b = c;b >= 1;b--) {
			for (int a = b;a >= 1;a--) {
				if (a + b > c) {
					count++;
				}
			}
		}
	}
	return count;
}

int main() {
	int n;
	cin >> n;

	cout << solve(n) << endl;
	
	return 0;
}

とりあえず１回提出してみたところ
「時間かかりすぎや、出直してこいm9(^Д^)ﾌﾟｷﾞｬー」と弾かれました。

それもそのはずで、計算量は $O(n^3)$ となってしまい
n=1,000,000の場合、到底1秒以内で答えを出せそうもありません。

もっと良いアルゴリズムを考えないといけないわけです。

まずはc=nの場合で全部の組み合わせを樹形図にしてみます。
f:id:AtelierOfYuzune:20160905181312p:plain

$a+b>c$ となる組み合わせは、
$b=n$ のとき、 $a=n,n-1,n-2,\cdots,1$ の $n$ 通り
$b=n-1$ のとき、 $a=n-1,n-2,\cdots,2$ の $n-2$ 通り
$b=n-2$ のとき、 $a=n-2,n-3,\cdots,3$ の $n-4$ 通り

※ただし、 $b=\frac{n}{2} + 1$ （ $\frac{n}{2}$ は切り捨て）ならば、
・cが奇数ならば $a=\frac{n}{2} + 1$ の $1$ 通り
・cが偶数ならば $a=\frac{n}{2} + 1,\frac{n}{2}$ の $2$ 通り

の総和（ただし $2b>c$ の場合のみ)となります。

この総和を $S_n$ と置くことにします。

$c=1$ のとき、 $b = 1 (= \frac{1}{2} + 1)$ より $S_1=1$
$c=2$ のとき、 $b = 2 (= \frac{2}{2} + 1)$ より $S_2=2$
$c=3$ のとき、 $b = 3 , 2(=\frac{3}{2} + 1)$ より $S_3= 3+1=4$
$c=4$ のとき、 $b = 4 , 3(=\frac{4}{2} + 1)$ より $S_4= 4+2=6$
…
となります。カッコ内の分数は全て切り捨てです。

これを並べてみると
$S_1=1$
$S_2=2$
$S_3=3+1=3+S_1$
$S_4=4+2=4+S_2$
$S_5=5+3+1=5+S_3$
$S_6=6+4+2=6+S_4$
となり、漸化式で表すことができます。

よって、一般項は
$S_k=S_{k-2}+k$
と表すことができます。

これを $c=1$ から $c=n$ までの総和を求めればよいので、
三角形は $\Sigma_{c=1}^n S_c$ 通りとなります。

後はこれをプログラムで実装すればいいのです。
※solve関数以外の場所は書き換えておりません。

int64_t solve(const int n) {
	int64_t count = 0;
	int64_t sum_o = 0, sum_e = 0;
	for (int i = 1;i <= n;i++) {
		if ((i & 1) == 0) {
			sum_o += i;
			count += sum_o;
		}
		else {
			sum_e += i;
			count += sum_e;
		}
	}
	return count;
}

このようにすることで $O(n^3)$ だったアルゴリズムを
$O(n)$ のアルゴリズムに改良することができました。