AtCoder Beginner Contest 453 C

https://atcoder.jp/contests/abc453/tasks/abc453_c

1回ずつ再帰的に進めばの計算量ですが、時間がギリギリです。

v <- scan("stdin", integer())

N <- v[1]
L <- v[2:(N+1)]

F <- function(L, i, x) {
    if(i == N + 1) {
        return(0)
    }
    
    x1 <- x + L[i]  # 正方向に進む
    n1 <- F(L, i+1, x1)
    if(x < 0 && 0 < x1) {
        n1 <- n1 + 1
    }
    x2 <- x - L[i]
    n2 <- F(L, i+1, x2)
    if(x2 < 0 && 0 < x) {
        n2 <- n2 + 1
    }
    max(n1, n2)
}

n <- F(L, 1, 0.5)
cat(n, "\n")

こうでなくて、経路は通りあるから、進む方向をビットで表すと整数にすることができます。その経路ごとに1回ずつ進んで、座標0をまたいだかを調べます。そのとき通りの経路についてまとめて計算すれば速いです。計算量はなので多いですが、こちらの方がだいぶ速いです。

dir <- function(a, i) {
    bitwAnd(bitwShiftR(a, i), 1) * 2 - 1
}

v <- scan("stdin", integer())

N <- v[1]
L <- v[2:(N+1)]
M <- 2**N

num <- rep(0, M)
pos <- rep(0.5, M)
for(i in 0:(N-1)) {
    new.pos <- pos + L[i+1] * dir(0:(M-1), i)
    num <- num + as.integer((pos < 0 & 0 < new.pos) |
                            (new.pos < 0 & 0 < pos))
    pos <- new.pos
}

cat(max(num), "\n")