Problem 86 - Project Euler
クモとアリ,最短経路などでググると有名らしい問題がでてくるけど,それよりは単純.頂点から頂点への移動,その最短距離が整数になる場合を数えるだけ.なんとなく三角形作ればいいんだなってのはすぐ分かる.
しかしかなり手間取った.三角形を作れば必ず最短経路になるってわけじゃないし,天井とか壁とか床とか区別しないってことに気付くのも遅れた.
is.int.side <- function(n,m){ floor(sqrt(n^2+m^2))^2==n^2+m^2 } paths <- function(n){ x <- (2:(2*n))[is.int.side(n,2:(2*n))] if(length(x)==0) return(0) ans <- 0 for(i in x){ if(n > i){ ans <- ans + floor(i/2) }else{ ans <- ans + ceiling(n-(i-1)/2) } } ans } sum.path <- 0 i <- 1 while(sum.path < 1e6){ i <- i+1 sum.path <- sum.path + paths(i) } i