r-statistics-fanの日記

統計好きの現場の臨床医の覚書のようなもの

paizaオンラインハッカソン:動的計画法 Rで挑戦

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」|paizaオンラインハッカソンLite

しえる (cielavenir) on Twitter

paiza_solutions/poh1_2.R at master · cielavenir/paiza_solutions · GitHub

PHP - POH Lite 天才火消しエンジニア霧島 0.01秒の解答 - Qiita

 

しえる さんの所で面白い記事を見た。

詳しくは しえる さんの記事を参照。

Rでは、時間切れになるとの記載がある。

動的計画法自体はじめてだが、何事も勉強。何とか挑戦してみる。


しかし、結論を言うと、最後まで完遂できなかった。

どうしてもケース3でひっかかる。

しえる さんの回避策でケース3を回避すると、他は完遂できた。

自分のスキルでは何故ケース3が通らないのかわからない。orz

原因判明 指数表示が原因でした。

options(scipen=10)を追加して通った!!!嬉しい!!!

 テストケース1:success 0.1秒
 テストケース2:success 0.1秒
 テストケース3:success 0.1秒
 テストケース4:success 0.1秒
 テストケース5:success 0.1秒
 テストケース6:success 0.21秒
 テストケース7:success 1.25秒

以下コード #しえる さんにアドバイス頂き、はてな記法を使ってみました

options(scipen=10)

data <- scan('stdin')

m <- data[1]
n <- data[2]
q <- data[1:n * 2 + 1]
r <- data[1:n * 2 + 2]

nc = as.integer(m + max(q) + 1)
temp2 <- dp <- integer(nc)
flag <- as.integer(c(1, rep(0, nc - 1)))

shift.n <- function(x, n) c(rep(0L, n), x[1:(length(x) - n)])

for (i in 1:n){
temp2 <- shift.n( (flag * (dp + r[i])), q[i])
dp <- (as.logical(dp * temp2) * ( (dp <= temp2) * dp + (dp > temp2) * temp2) + (dp * temp2 == 0) * (dp + temp2))
flag <- as.logical(dp != 0)
flag[1] <- 1L
}

dp[1:m] <- 0
ans <- min(dp[dp != 0])

cat(ans, "\n", sep="")