Problem 76

Problem 76 - Project Euler
アンチョコ見てしまったけれども今回は久しぶりに上手くできたと思う。
200msくらい。
そしてProblem 76はアレです。分割数! そう、数学ガール!

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

っても本に解答載ってるわけじゃないけど。
いやまあ載ってると言えば載ってる。分割数の一般項が。ただ読んだ人なら分かると思うけど、ちょっと試行錯誤で思いつくのは厳しい。
見てしまったアンチョコはこれ。

概要はこんなかんじ。
ある数nについてr個に分割する方法を考えp(n,r)によって分割パターンの個数を表わすとすると、明かに

  • p(n,n)=1
  • p(n,1)=1

それ以外のとき、+1を含む分割パターンは+1の項を一つ減らすことでp(n-1,r-1)と等しくなり、+1を一つも含まない分割パターンでは各項から1ずつ引くことでp(n-r,r)と等しくなる。よって、

  • p(n,r)=p(n-1,r-1)+p(n-r,r)

これは再帰を使ったら簡単に書ける。

pn.part <- function(n,r){
  if(n==r || r==1) return(1)
  if(n < r) return(0)
  return(pn.part(n-1,r-1) + pn.part(n-r,r))
}
ans <- 0
for(i in 2:100){
  ans <- ans + pn.part(100,i)
}
ans

ただしこれは見易いだけで1時間回したって終わらない。
行列にメモって計算したらすぐ終わる。

pn.parts <- matrix(rep(0,1e4),100)
for(n in 1:100){
  for(r in 1:n){
    if(n==r || r==1){
      pn.parts[n,r] <- 1
    }else{
      pn.parts[n,r] <- pn.parts[n-1,r-1]
      if(n-r >= r) pn.parts[n,r] <- pn.parts[n,r]+pn.parts[n-r,r]
    }
  }
}
sum(pn.parts[100,1:99])