【Project Euler】Problem 15: 格子状の道

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 15. 格子状の道

原文 Problem 15: Lattice paths

問題の要約：20 x 20の格子状の道を左上から右下まで行くルートは何通りあるか求めよ

各格子点に入る道は、上からと左からの2つで、それぞれの前の格子点までのルートの数を足せばよいので、パスカルの三角形(Wikipedia) になることが分かります。パスカルの三角形は前の行を一つずらして足して行きます。n=2の時は4行目まで求めて、その真ん中の値が答えになっています。

import numpy as np
n = 2
p = np.array([1])
for i in range(2*n):
  p = np.append(p, 0)+np.append(0, p)
  print(p)
print(f"Answer : {p[n]}")
#[1 1]
#[1 2 1]
#[1 3 3 1]
#[1 4 6 4 1]
#Answer : 6

もちろんパスカル三角形のn行r列は組合せの数$nCr$なので、sympyのbinomialでも簡単に求めることが出来ます。

from sympy import binomial
n = 20
print(binomial(2*n, n))

（開発環境：Google Colab）