[Project Euler] Problem 15

Problem 15

これも計算機を使わないで解いた方が速い問題。
n x n grid で考えると、2n ステップの中から n 個右を選ぶということだから、
_{2n}C_n を計算すればいい。つまり、(2n)! / (n!)^2 。

もうちょっと計算機っぽく考えると、nx x ny のグリッドの場合、最初に右に行くか下に行くかで、
f(nx,ny) = f(xn-1,ny) + f(xn,ny-1)
但し、
f(0,_) = f(_,0) = 1
を解けば良いが、最初の式は実は _nC_r = _{n-1}C_r + _{n-1}C_{r-1} の事である。
実際にはこのままではf(nx,ny)回の関数呼び出しが発生するので、メモ化する。

import scala.collection.mutable.HashMap
import java.math.BigInteger

object P015 {
  val map:HashMap[Tuple2[Int,Int],Long] = new HashMap()
  def f(nx:Int, ny:Int):Long = map.get(Tuple2(nx,ny)) match {
    case Some(x) => x
    case None => {
      val z:Long = (nx,ny) match {
        case (0,_) => 1
        case (_,0) => 1
        case (x,y) => f(x-1,y) + f(x,y-1)
      }
      val zz = map.put(Tuple2(nx,ny),z)
      z
    }
  }
  def main(args:Array[String]) {
    println(f(20,20))
    println(40L/20*39*38/19*37*36/18*35*34/17*33*32/16*31*30/15*29*28/14*27*26/13*25*24/12*23*22/11*21/10/9/8/7/6/5/4/3/2/1)
  }
}