Problem 74

Problem 74 - Project Euler
15秒。どうも上手いやりかたが分からない。スレッドを良く読んでみるべきか。
というか、CやC++の人を見ていると結構brute forceなやり方でも常識的な時間で終わっている。Rでこの先生きのこるにはどうすれば…

options(scipen=1)
toDig <- function(n){
  as.numeric(strsplit(as.character(n),"")[[1]])
}
toNum <- function(n){
  sum(rev(n)*10^(0:(length(n)-1)))
}
non.rep.terms <- function(n,count=0){
  if(n==871 ||
     n==872 ||
     n==45361 ||
     n==45362) return(count + 2)
  if(n==169 ||
     n==1454||
     n==363601) return(count + 3)
  if(n==sum(factorial(toDig(n)))) return(count + 1)
  return(non.rep.terms(sum(factorial(toDig(n))),count+1))
}

ans <- 0
for(n1 in 1:9){
  for(n2 in 0:n1){
    for(n3 in 0:n2){
      for(n4 in 0:n3){
        for(n5 in 0:n4){
          for(n6 in 0:n5){
            cand <- toNum(c(n6,n5,n4,n3,n2,n1))
            if(non.rep.terms(cand)==60){
              c.d <- toDig(cand)
              one <- length(c.d[c.d==1])
              d <- length(c.d)
              divs <- factorial(table(c.d))
              plus <- factorial(d)
              for(i in divs) plus <- plus/i
              ans <- ans + (ifelse(one==0,
                                   plus,
                                   plus*(2^one) -
                                   factorial(d-1)/
                                   (factorial(d-one)*factorial(one-1))*
                                   factorial(d-1)
                                   ))
            }
          }
        }
      }
    }
  }
}
ans

桁ごとの階乗の和を計算するのだから、10^6以下のすべてをあたる必要はない。
また、1!と0!はいずれも1なので0を含む数字もあたらなくてよい。
ひとつ候補がみつかったら、桁を入れ替えて得られる数値の個数を計算する。
それに対して1を0に置き換えられるパターンの数を乗ずる。
最上位にある1は置き換えられないので、その分は引く。
得られた組み合わせの個数を解答に足す。
以上繰り返し。