Problem 85

Problem 85 - Project Euler
長方形の中に長方形を入れる方法がいくつあるのか、200万通りに最も近い入れ方を有す長方形の面積はどれだけか、という問題。
500msくらい。
最初解き方だけが分かってしまってなんで解けるのかよく分からなかった。でもまあ分かってしまえばなんてことなかった。

target <- 2e6
limit <- sqrt(target)*2
side <- (1:limit)*(1+1:limit)/2
ans <- 0
min.diff <- target
for(i in 1:limit){
  min.id <- which.min(abs(side[i]*side[1:i]-target))
  candi <- abs(side[i]*side[min.id] - target)
  if(min.diff > candi){
    ans <- i * min.id
    min.diff <- candi
  }
}