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

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

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

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

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

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

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

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

~~自分のスキルでは何故ケース３が通らないのかわからない。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="")

r-statistics-fanの日記

統計好き人間の覚書のようなもの

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