Problem 115

R Project Euler

Problem 114を難しくした問題．ユニットの長さをn，ブロックの最低長さをmとしたとき，ブロックの入れ方のパターン数をF(m, n)で表す．
例えばF(3, 29) = 67315といった具合で，F(3, 50)ならProblem 114の答えである．
F(50, n)について，値がはじめて1,000,000を超えるnの値を求めよ，という問題．
Problem 114とほとんど同じやり方で解けるので特に苦労するところはなかった．370ms．

f <- function(m, n){
  plus.block <- function(pat){
    new.pat <- rep(0, n+1)
    new.pat[1] <- sum(pat[c(1, (m+1):(n+1))])
    new.pat[2:m] <- pat[1:(m-1)]
    new.pat[(m+1):(n+1)] <- pat[m:n]
    return(new.pat)
  }
  block <- rep(0, n+1)
  block[c(1, m+1)] <- 1
  for(i in (m+1):n){
    block <- plus.block(block)
  }
  sum(block)
}

i <- 51
while(f(50, i) < 1e6) i <- i + 1
i