백준 18527번 All Kill

문제 요약

문제가 n개 주어지고 시간이 t만큼 주어진다.

문제를 푸는 과정은 두 단계로 나뉜다. 풀이가 생각난다. 코딩을 한다.

각 문제 별로 코딩에 걸리는 시간이 다르며, 각 문제의 풀이가 떠오를 확률은 각 분마다 $\frac{1}{\text{남은 분 수}}$이다.

풀이가 떠오르면 바로 코딩을 시작하는데, 항상 풀이가 떠오른 문제들 중에서 번호가 낮은 문제부터 코딩을 한다. 즉, 7번 문제를 코딩 중인데 2번 문제의 풀이가 떠올랐다면 2번 문제의 코딩을 바로 시작한다. 반대로 2번 문제을 코딩하는 도중에 6, 7번 문제의 풀이가 떠올랐다면 2번 문제의 코딩을 끝내고 6, 7번을 순서대로 코딩한다.

이와 같이 문제를 푼다고 했을 때, 모든 문제를 풀되, 코딩 중에 방해받지 않고 모든 문제를 풀 확률을 $p$라고 하자.

각 문제의 코딩 시간 $x_i$가 주어질 때, $pt^n$의 값을 구하여라

$n \le 10^5$, $t \le 10^8$이다.

풀이

일단 확률을 구하는 것은 매우 짜증나는 작업이다. 경우의 수를 구하는 거로 바꿔서 생각을 해보자.

이게 가능한 이유는 각 문제가 시각 $i$에 떠오를 확률은 모든 시각에 대해서 $1/t$로 동일하기 때문이다. 간단히 식을 적어보면 제일 처음 분모 $t$랑 마지막 분자 $1$ 외에는 다 지워진다.

해당 문제는 길이가 $t$인 선분 상에 길이가 $x_i$인 선분들을 서로 겹치지 않게 놓는 것과 같은 작업이 된다. 그리고 이 $x_i$인 선분을 놓는다는 것을 이 선분이 놓일 곳의 시작점을 정하는 것으로 생각하자.

이러면 이제 문제에서 원하는 값은 선분을 놓는 valid한 경우의 수가 된다.

문제의 조건 중에서 어떤 문제를 코딩 중인데 번호가 앞서는 문제의 풀이가 떠오르면 코딩을 넘겨주는 조건이 있다.

이를 생각해보면 $x_{i+1}$을 이미 놔서 $[l, r]$을 점유중이라고 하자. 그러면 $x_1, \ldots , x_i$는 $[l, r]$에 놓일 수 없다. 이러한 일이 발생하면 코딩중인 문제를 가로채는 일이 발생하는 것과 같다.

따라서, $a_n$부터 시작해서 놓도록 하자. 처음엔 모든 직선이 비어있다. 그러면 이제 $a_n$을 놓을 수 있는 곳이 얼마나 될까?

아무 곳에나 놓을 수 있겠지만 길이가 $x_n$은 되어야 하나 직선의 끝에서부터 $x_n - 1$칸은 놓을 수 없다.

그러면 n번째 선분을 놓을 수 있는 곳은 $t - (x_n-1)$이 된다.

그다음 n-1번째 선분을 놓을 수 있는 곳은 어디일까? $x_n$이 놓여 있는 곳을 $[l, r]$이라고 하자. 그러면 $[l-1, r]$에 놓이면 안된다. 만약 이 곳에 놓였다는 것은 n번 문제의 코딩 중에 풀이가 떠올랐다는 뜻이고 그러면 코딩을 가로채야 한다.

그런데 왜 $l$에는 놓여도 될까? n번째 선분과 n-1번째 선분이 같은 곳에 놓였다는 것은 동시에 문제의 풀이가 떠올랐다는 것이고 그러면 n-1번 문제부터 코딩을 시작해서 인터럽트가 발생하지 않는다. 그리고 n번 문제는 n-1번 문제가 끝난 뒤로 밀린다.

따라서, n-1번째 선분을 놓을 수 있는 곳은 $t - (x_n-1) - (x_{n-1}-1)$이 된다.

이런 식으로 $i$번째 선분을 놓을 수 있는 곳은 $t - \sum_{i+1}^n (x_j-1)$이 된다.

여기서 중요한 부분을 하나 빠뜨리고 얘기했다. 우리가 선분을 놓고 있는 곳은 길이가 t인 선분이다.

따라서 이전에 놓은 선분들의 위치에 따라서 같은 곳에 놓은 선분이 여러 개 일 때, 밀려나갈 공간이 모자랄 수도 있다.

이러한 일이 안 일어나도록 하는 경우의 수를 일일이 고려해야 할까? 이걸 다 고려할 생각을 하면 막막해진다.

하나 좋은 방법은 선분이 아니라 칸을 하나 더 추가해서 원으로 만들어 버린 다음에 그 위에 놓는 것이다. 그러면 원이기 때문에 밀어버릴 수 있다.

이러면 위 문제는 해결되었다. 다만, 추가로 고려해줘야 할 것이 있다. 원 위에 놓은 것이기 때문에 시작점과 끝점을 정해야 하고, 중복으로 세지는 경우도 있을 것이다.

시작점과 끝점을 정하는 경우의 수는 $T+1 - \sum x_i$이다. 중복으로 세는 횟수는 $T+1-\sum x_i+N$이다. 이를 각각 곱해주고 나눠주면 답이 나온다.

시간복잡도는 $O(N)$이라고 볼 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll N, T;

ll modpow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b&1) ret = ret * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> T;
    ++T; vector<ll> x(N);
    for(ll &i:x) cin >> i;
    ll ans = 1;
    for(int i=N-1;i>=0;--i) {
        T -= x[i]-1;
        ans *= T;
        ans %= mod;
    }
    ans *= T-N;
    ans %= mod;
    ans *= modpow(T,mod-2);
    ans %= mod;
    cout << ans << '\n';
    return 0;
}