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は置き換えられないので、その分は引く。
得られた組み合わせの個数を解答に足す。
以上繰り返し。