Problem 191

http://projecteuler.net/problem=191

ある学校では、きちんと出席し遅刻をしない生徒に対し賞金を出している。3日以上連続して欠席したり、1日より多く遅刻すると賞金は得られない。
n日間の各生徒の出席状況は、3つの文字、L(Late、遅刻)、O(On time、出席)、A(Absent、欠席)からなる文字列で表現できる。
4日間ならば81通りの文字列が作れるが、そのうち賞金を得られる文字列は次の43通りである。

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

30日間の場合、賞金を得られる文字列は何通りあるだろうか。

最初、2進数で文字列を作って数え上げようとしたけどさっぱりだった。
2^30≒10億なので、多少計算量を削った所でRでは無理だとは思いつつ回してしまう…。

#### 終わらない… #####
library(gmp)
## n桁になるように左に0をつけた2進数表現
fill.zero <- function(bz, n){
  bz <- as.character(as.bigz(bz), 2)
  if(nchar(bz) < n){
    paste(paste(rep(0, n-nchar(bz)), sep="", collapse=""),
          bz, sep="")
  } else {
    bz
  }
}

## 0の個数をカウント
count.zero <- function(z){
  length(gregexpr("0", z)[[1]])
}

day <- 30
limit <- 2^(day)
n <- 0
cnt <- 0
while(n < limit){
  z <- fill.zero(n, day)
  ## 賞をもらえるか?
  if((fnd <- regexpr("111", z)[1]) < 0){ # もらえる
    cnt <- cnt + 1 + count.zero(z)       # 許容される休みパターン含
  } else {                               # もらえない
    n <- n + 2^(day - fnd - 2)           # 不要パターンスキップ
    next
  }
  n <- n + 1
}
cnt

終わらない計算を待つ間ググっていたら

簡単に漸化式が書ける。
(Project Euler 191 - 桃の天然水)

とのことだったのでちょっと紙とペン使ったらすぐ解けた。少しは頭を使うということをしないとダメだ。
例えば、

  • 連続した休み0日、遅刻0日

という状態の文字列を1日分増やすとすると、

  • 連続した休み0日、遅刻0日
  • 連続した休み1日、遅刻0日
  • 連続した休み0日、遅刻1日

という状態が作り出せる、という具合。

day <- 1                                # 1日目のパタン
##    00 10 20 01 11 21    左:A 右:L
D <- c(1, 1, 0, 1, 0, 0)
limit <- 30
while(day < limit){
  day <- day + 1
  D <- c(sum(D[1:3]), D[1], D[2],
         sum(D), D[4], D[5])
}
sum(D)