134468のようにどの桁の数字も左の桁の値以上である数字をincreasing numberと呼ぶ．逆に66420のようにどの桁の数字も左の桁の値以下である数字をdecreasing numberと呼ぶ．
そして，increasing numberでもdecreasing numberでもない数字を"bouncy" numberと呼ぶ．
自然数の中でbouncy numberが占める割合は調べる範囲を広げるほど増えて行く．その値以下の数字を調べたとき，bouncy numberの割合がちょうど99%となる最初の数字は何か．
最初brute forceでやったら1時間くらいかかってどうしようもなかったので，少し飛ばし飛ばしに調べるようにした．結果として大分汚い．しかも16秒かかっている．
それにbouncy numberの割合は単調増加する訳じゃないので確実に答えを発見できるかどうかというと微妙なところ．
でもforum見ると割とbrute forceでやってる人が多い…．Rだとforループが100万回程度でも大分時間がかかって，例えば
for(i in 1:1e6) mean(1:3)
なんていうコードでも20秒弱かかるので，かなり注意してうまいやり方を探さないとこの先生きのこれない．
dig2vec <- function(n) floor((n / 10^(floor(log(n, 10)):0)) %% 10) lastdig <- function(n) n %% 10 last2dig <- function(n) c(floor(n/10) %% 10, n %% 10) is.inc.num <- function(n) !(sum(diff(dig2vec(n)) < 0) > 0) is.dec.num <- function(n) !(sum(diff(dig2vec(n)) > 0) > 0) is.bouncy <- function(n) !(is.inc.num(n) || is.dec.num(n)) limit <- 0.99 i <- 100 cnt <- 0 f <- FALSE slow <- FALSE while(cnt/i < limit){ if(cnt/i >= limit) break if(!f) i <- i + 1 f <- FALSE if(is.inc.num(i)){ i <- i + 10 - lastdig(i) - 1 next } if(is.dec.num(i)){ i <- i - diff(last2dig(i)) next } if(!slow){ for(j in 5:1){ if(i %% 10^j == 0){ tmp <- (i / 10^j) %% 10 i <- i + 10^(j - 1) * tmp cnt <- cnt + 10^(j - 1) * tmp f <- TRUE if(cnt/i >= limit){ i <- i - 10^(j - 1) * tmp cnt <- cnt - 10^(j - 1) * tmp slow <- TRUE } break } } } if(f) next cnt <- cnt + 1 } i cnt
