paizaオンラインハッカソンの問題をRで挑戦してみる

女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2

で、面白そうな企画をやっていたようだ。（過去形）

でも、R言語は選択肢に無い。

そもそも、Rがあったとしても、条件に合うようにインプットや

アウトプットをどうすりゃいいのかも分からない。

ただ、与えられたタスクを実装することはできそうだ。

参加してないから問題が分からんので、最大のH*Wで、すべての

ウィジェットの組合せの解を出力することにする。

Rでやってみた。

##ウィジェット

set.seed(1)

H <- 130
W <- 130

N <- H * W

S_T <- expand.grid(1:H, 1:W)   #評価されるウィジェットが分からんのですべての組合せを計算することにする。

D <- matrix(as.integer(0), ncol = W, nrow = H)

d1 <- sample(0:1, N, replace = TRUE, prob = c(0.95, 0.05))  #そこそこ隙間がある感じの問題にする

D <- matrix(d1, ncol = W, nrow = H, byrow = TRUE)

f2 <- function(D = D, H = H, W = W){
ans <- array(as.integer(0), dim = c(H + 1, W + 1, W))
ans.no <- matrix(as.integer(0), ncol = W, nrow = H)

temp <- cbind(-D + 1, cbind(rep(0, nrow(D)))) ##0の列追加
ans[,,1] <- rbind(temp, rbind(rep(0, ncol(temp)))) #0の行追加
ans.no[1,1] <- sum(ans[,,1]) #1*1の解の数

i <- 2
flag0 <- 1
while (flag0 != 0 && i <= ncol(D)){
ans[,,i] <- ans[,,(i -1)] * ans[, c(2:dim(ans)[2], 1), (i -1)] #1*iのウィジェットの配置可能位置
flag0 <-ans.no[1,i] <- sum(ans[,,i])  #1*iのウィジェットの答え
i <- i + 1
}

for (k in 1:ncol(D)){
flag1 <- 1
j <- 2
while (flag1 != 0 && j <= nrow(D)){
ans[,,k] <- ans[,,k] * ans[c(2:dim(ans)[1], 1),,k]
flag1 <- ans.no[j, k] <- sum(ans[,,k])
j <- j + 1

}
next
}
return(ans.no)
}

> system.time(f2(D,H,W))
ユーザ システム 経過
0.71 0.00 0.70

女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2

を見ると、

テストケース７（大規模データ）の 最速・最遅実行時間です。

言語	最速実行時間	最遅実行時間	通過数 / 受験数
Java	0.04 秒	5.98 秒	327 / 1364 提出
PHP	0.09 秒	9.42 秒	245 / 922 提出
Ruby	0.05 秒	9.92 秒	127 / 754 提出
Python	0.16 秒	8.43 秒	142 / 674 提出
Perl	0.04 秒	9.79 秒	40 / 162 提出
C	0.01 秒	2.78 秒	290 / 1100 提出
C++	0.01 秒	2.95 秒	375 / 1110 提出
C#	0.01 秒	5.99 秒	193 / 762 提出

130*130で0.71秒というのは、それなりに遅そう。

まだまだ修業が必要のようだ。できるだけ行列を使うように

したつもりなんだが。ざんねん。

なお、３００＊３００のすべての組合せを計算すると

system.time(f2(D,H,W))
ユーザ システム 経過
6.19 0.03 6.22

と６秒もかかってしまった。

cってさすがに速いねー。0.01秒って。