백준 21343번 Great Expectation

문제

스피드런을 진행하려고 한다. $n, r, m$이 주어지는데 $n$은 이상적으로 진행했을 때의 걸리는 시간이고 $r$은 깨고자 하는 기록이다. 즉, 전체 시간을 $r$보다 작게 스피드런을 끝내고 싶다.

스피드런 도중에는 $m$개의 이벤트가 있는데 이 이벤트에 성공하면 그대로 진행하는 것이고, 실패하면 추가적으로 시간을 사용하게 된다.

이벤트에 대한 정보는 $t, p, d$로 주어지는데 각각 이벤트가 일어날 시각, 성공확률, 실패 시 추가로 드는 시간이다. 스피드런 도중에 언제든지 리셋을 할 수 있다.

이런 상황에서 전체 진행시간을 $r$보다 짧게 만드는 데 걸릴 시간의 기댓값을 구하시오.

$ 2 \le n \lt r \le 5000$, $ 1 \le m \le 50$, $ 1 \le t \lt n$, $ 0 \lt p \lt 1$, $ 1 \le d \le 1000$

풀이

문제를 해석해놨지만 잘 이해가 안될 수도 있다. 첫번째 예제를 보자. 모든 이벤트에 성공하면 100초가 걸린다. 우리의 목표는 111초보다 짧게 끝내는 것이다.

20초에 이벤트가 있는데 이에 성공하면 무탈하게 지나는 것이고 실패하면 10초를 추가로 사용한다는 것이다. 여기서 10초를 사용했으니 하나라도 실패하면 기록을 갱신할 수가 없다. 그러면 실패하자마자 리셋하고 다시 도전하는게 시간 상으로 더 빠르게 기록 갱신을 할 확률이 높다.

만약에 리셋 없이 그대로 진행한다고 치면 10초 밀렸으니까 90초에 두번째 이벤트를 만나고 95초에 세번째 이벤트, 100초에 네번째 이벤트, 105초에 다섯번째 이벤트를 만난다. 여기서 전부 성공하고 끝내면 110초만에 끝내고 성공이다. 이 경우가 아니면 전부 실패다.

위에서 말했던 내용 중에 중요한 관찰이 있다. 리셋을 할지 말지는 이벤트를 실패했을 때만 결정하면 된다. 이 외에는 리셋을 할 이유가 없다. 이를 통해서 DP를 생각해볼 수 있다.
$$
dp(i, t)=\text{i번째 장애물에서 t초만큼 추가로 썼을 때, 성공까지 걸릴 시간의 기댓값}
$$
그러면 이제 우리가 원하는 값은 $dp(0, 0)$이 된다. 여기서 시간을 추가로 사용했다는 것은 어떤 이벤트에 실패 해서 $d_i$만큼 사용했다는 것이다.

이렇게 dp식을 세우고 나면 상태 전이는 아래처럼 생각할 수 있다.
$$
dp(i, t)=p_i(dp(i+1, t)+t_{i+1}-t_i) + (1-p_i)\min(dp(0,0), dp(i+1, t+d_i)+t_{i+1}-t_i+d_i)
$$
만약 이벤트에 성공했다면 그냥 진행하면 된다. 이벤트에 실패햇다면 선택지가 두가지가 있다. 리셋하거나, 진행하거나.

이것을 식으로 나타낸 것이다. 이 식의 문제점이 하나 있다. 우리가 원하는 값은 $dp(0,0)$인데 이 값이 채워져 있어야 다른 값들도 채워진다는 것이다.

여기서 생각할 수 있는 것이 우리가 임의로 이 값을 정하자는 것이다. 그리고 이를 토대로 dp값을 전부 채워놓은 다음에 임의로 정한 값과 그 값을 토대로 계산한 $dp(0,0)$를 비교하자.

만약 우리가 임의로 정한 값이 더 높다면 높게 정했다는 것이고, 더 낮다면 우리가 너무 낮게 정했다는 것이다. 이를 토대로 이분탐색을 진행하면 답을 찾을 수 있다.

이게 왜 이분탐색이 되는가에 대해서는 고민을 꽤 했는데 만약 $dp(0,0)$이 너무 작다면 $\min$ 안에서 $dp(0,0)$을 선택하면 안될 때 선택할 거고, 너무 크다면 선택해야 될 때 선택을 못하니까 전체 값들이 점점 커지거나 작아지는 상황이 우리가 정한 값과 계산한 값의 대소관계와 같을 것이다.

시간복잡도는 $O(nmlogT)$로 $T$는 가질수 있는 제일 큰 값인데 이 값이 대략 25억쯤 될 것이다. 그런데 실수이분탐색이니까 국룰 100번 돌려서 사실 별 상관 없다.

#include<bits/stdc++.h>
using namespace std;
using ld = double;
ld x;
ld dp[55][5005];
bool vis[55][5005];
int n, r, m;
int a[55], d[55];
ld p[55];

ld go(int idx, int t) {
    if(idx == m && t < r) return 0; // beat record
    if(t >= r) return x;   // must reset
    if(vis[idx][t]) return dp[idx][t];
    dp[idx][t] = 0;
    dp[idx][t] += p[idx] * (a[idx+1] - a[idx] + go(idx+1, t));
    dp[idx][t] += (1-p[idx]) * min(x, a[idx+1] - a[idx] + d[idx] + go(idx+1, t+d[idx]));
    vis[idx][t] = true;
    return dp[idx][t];
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> n >> r >> m;
    for(int i=1;i<=m;++i) cin >> a[i] >> p[i] >> d[i];
    a[++m] = n;
    a[0] = 0;
    r -= n;
    ld lo = 0, hi = 1e18;
    for(int i=0;i<100;++i) {
        x = (lo+hi)/2.0;
        memset(vis, false, sizeof(vis));
        ld t = go(0, 0);
        if(t < x) hi = x;
        else lo = x;
    }
    cout << fixed << setprecision(15) << x << '\n';
    return 0;
}