Project Euler 015を解いてみる。「格子経路」

Project Euler 015

015

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, 20×20 のマス目ではいくつのルートがあるか.

->次の問題

考え方

中学か高校の数学でやったことのある問題ですね。
どんなルートを通るにしても右に20回、下に20回の計40回の移動をすることは確定しているので、
40個の動作の中から「下へ行く」をする20箇所を選ぶ組み合わせ問題と考えられます。

{}_{40} C_{20} = \frac{40!}{20!20!}

コード

euler015.py

def main():
    """
    go downが20回、go rightが20回の計40回の動作がある。
    40個の動作の中からgo downをする20箇所を選ぶ組み合わせ問題と考えられる。
    40C20 = (40*39* ・・・ *22*21) / (20*19* ・・・ *3*2)
    :return:
    """
    n = 20
    ans = 1
    for i in range(n + 1, n * 2 + 1):
        ans *= i
    for i in range(2, n+1):
        ans //= i
    print(ans)


if __name__ == '__main__':
    from time import time as t
    start = t()
    main()
    print(t() - start, 'sec')

paizaにて実行
結果 137846528820 9.775161743164062e-06 sec
計算量も大したことはないので、とくにひねりもなくそのまま計算しました。