Problem 173

正方形の輪郭と正方形の"穴"を持ち,縦横に対象なものをsquare laminaと呼ぶことにする.正方形のタイルを並べてsquare laminaを作成することを考えると,タイルを32枚ちょうど使うのであれば2種類のsquare laminaを作成できる.
もし100枚のタイルを使うのであれば(100枚以下の何枚を使用してもいい),41種類の異なるsquare laminaを作成できる.
100万枚以下のタイルを使って作成できるsquare laminaは何種類あるか.

最初あまり考えずに全てのパターンを数え上げる方法でやって9秒かかった.

nmax <- 1e6
count <- 0
## perimeters a (start from 3*3)
pa <- rev(seq(8, nmax, 8))
## perimeters b (start from 4*4)
pb <- seq(12, nmax, 8)

countla <- function(p, nmax){
  count <- 0
  for(i in 1:length(p)){
    cntmp <- 0
    tmp <- p[i]
    while(tmp <= nmax && i + cntmp <= length(p)){
      cntmp <- cntmp + 1
      tmp <- tmp + p[i + cntmp]
    }
    count <- count + cntmp
  }
  return(count)
}
countla(pa, nmax) + countla(pb, nmax)

forum読んだらもっといい方法が書いてあった.これだと0ms.範囲を10^12以下に広げても10ms程度.タイルで作成されたsquare laminaを四隅にある正方形と四辺にある長方形に分解して考えるのがポイント.

countlaminae <- function(nmax){
  a <- nmax/4
  b <- sqrt(a)
  sum(floor(a/(1:b))) - b*(b+1)/2
}
countlaminae(1e6)