Problem 15 - にたまごほうれん草アーカイブ

Problem 14がなかなか解けないので先に15を解くことにする。
14の計算が終わらないのはきっとアルゴリズムが悪いんだな…。

2x2のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。
では、20 × 20 のマス目ではいくつのルートがあるか。
Problem 15 - PukiWiki

これは簡単な組み合わせの問題で、 ${}_{40} C_{20}$ を解けばよい。
ただ、これを計算機でバカ正直に解こうとすると、階乗の計算であっという間にオーバーフローしてしまうので、少しだけ工夫をした。

$a_{k} = {}_{n} C_{k} = \frac{n!}{k!(n-k)!$ とすると、
$a_{k-1} = {}_{n} C_{k-1} = \frac{n!}{(k-1)!(n-k+1)!$
$k>1$ のとき $a_{k-1} \neq 0$ なので、
$\frac{a_{k}}{a_{k-1}} = \frac{n-k+1}{k}$
すなわち、 $a_{k} = \frac{n-k+1}{k} a_{k-1}$ となり、 $a_{1} = 40$ から漸化式を計算する。

# 久しぶりに数式を使ったので正直自信がないですが

#include <stdio.h>
typedef long long llong;

llong comb(llong n, llong k) {
    if (k == 1) {
        return n;
    } else {
        return ((n-k+1) * comb(n, k-1) / k);
    }
}

void problem015()
{
    llong ans;

    /* solve this problem here */
    ans = comb(40, 20);

    printf("%s: answer = %lld\n", __FUNCTION__, ans);
}

int main(int argc, char* argv[]) 
{
    problem015();
    return 0;
}

実行結果

$ ./problem015
problem015: answer = 137846528820

解答があっているかどうかぐぐって調べててわかったんだけど、この問題はパスカルの三角形とか言うみたいね。