[BOJ 17694] Sparklers

https://www.acmicpc.net/problem/17694

 

JOI spring camp 16/17 문제. 예전에 친구와 R&E 가서 얘기했던 문제다. 최근에 다시 잡고 생각을 하다가 어느 정도 풀만해 보이는 수열 문제로 바꿨는데, 그 이후 진전이 없다가 오늘 그림판에 열심히 그리면서 풀이를 찾아 풀었다. 뭔가 그리디적인 풀이가 있는 것으로 보이나 나는 $dp$ 경로를 최적화하는 방식으로 생각했다.

 

문제

$N$명의 사람이 각각 $T$초동안 타는 불꽃을 들고 서 있고, $K$번째 사람의 불꽃만이 시간 $0$에 타기 시작한다. 한 사람이 불꽃을 두 번 이상 태울 수는 없다. 0초에 $i$번째 사람은 $X_i$에 서 있고, $X_i \leq X_{i+1}, X_1=0$을 만족한다. 두 사람이 같은 좌표에 있을 때 불꽃을 옮길 수 있고, 모든 사람들은 최대 속력 $s$로 움직일 수 있다고 하자. 모든 사람의 불꽃이 최소 한 번은 타도록 하기 위한 $s$의 최소는?

 

풀이

답을 $v$라고 가정하고 모든 사람이 불꽃을 태울 수 있는지 판별하는 문제를 풀 수 있다고 한다면, 이분 탐색을 통해 최소 $s$를 찾을 수 있다. 이제 속력을 $v$라 두고 모든 사람이 불꽃을 태울 수 있는지 판별하자.

 

우선 자명하게, 불꽃이 최소 한 번은 탔던 사람들이 연속한 구간으로 존재할 것이다. 둘 째로 불꽃이 한 번도 타지 않은 사람은 모두 불꽃이 최소 한 번은 탔던 사람들의 구간 쪽을 향해 속력 $v$로 이동하는 것이 최적일 것이다. 또 불꽃은 항상 꺼지기 직전에 전달해도 충분하다. 예를 들어, a가 원래 오른쪽에 있던 b에게 전달한 뒤 꺼질 때까지 시간이 남는 최적해가 있다고 하자. b가 설령 왼쪽으로 이동하는 a를 a의 불꽃이 다 탈 때까지 따라간다고 하더라도 오른쪽의 다른 사람들과의 상대 거리는 변하지 않기 때문에 꺼지기 직전까지 a를 따라다닌 후 불꽃을 받아 오른쪽으로 이동해도 오른쪽 부분에 대해 상황이 동일하다. 반대 방향도 비슷하게 생각할 수 있다. 이러한 관찰을 한다면, 불꽃이 타고 있는 사람은 한 명이라고 생각해도 충분함을 알 수 있다. 또한 모든 사람들의 상대적 위치는 변하지 않으며 아직 불꽃이 타지 않은 사람들이 불꽃이 타고 있는 한 명에게 다가가는 것으로 생각할 수 있다.

 

여기서 조금 재밌는 생각을 할 수 있는데, 불꽃이 타고 있는 한 명의 좌표를 범위로서 들고 있다고 가정해보는 것이다. 즉, 불꽃이 타고 있는 사람의 좌표의 가능한 범위를 설정하는 것이다. 그리고 이를 중심 구간이라 하자. 초기에 이 중심 구간은 $[X_K, X_K]$이다. 만약 다음으로 불꽃을 전해줄 사람이 오른쪽에 있는 사람이고 원래 구간이 $[l, r]$이었다면, 전해주기 직전에는 구간이 $[l-vT, r+vT]$로 변할 것이다. 이후 오른쪽 사람의 전해주기 직전 좌표가 $x$였다면, 이 사람이 있을 수 있는 범위는 $[x-vT, \infty)$로 생각할 수 있다. 이 둘의 교집합이 새로운 중심 구간이 되고, 이 구간은 $[x-vT, r+vT]$로 생각할 수 있다. 다만 여기서 중심 구간 왼쪽의 사람들은 좌표가 $x$였다면 $x+vT$가 되고, 오른쪽 사람들은 $x$였다면 $x-vT$가 된다. 여기서 한 가지 재밌는 짓을 할 수 있는데, 모든 좌표에 $vT$를 빼 보는 것이다. 그러면 중심 구간은 $[x-2vT, r]$, 왼쪽 사람들의 좌표는 그대로, 오른쪽 사람들의 좌표는 $x$가 $x-2vT$가 되는 꼴이 된다. 왼쪽에 대해서도 비슷하게 생각하면, 구간이 $[l, x+2vT]$, 오른쪽 사람들은 그대로, 왼쪽 사람들은 $x$가 $x+2vT$가 되는 꼴이다.

 

위와 같은 관찰을 거쳤다면, 결국 이 문제는 어떤 구간의 하한과 상한으로 가능한 배열이 두 개 있을 때 상한 또는 하한을 해당 배열의 다음 값으로 바꾸는 연산을 구간이 공집합이 되지 않도록 적당히 수행하며 배열의 모든 값들을 훑을 수 있는지 판별하는 문제로 바뀌게 됨을 발견할 수 있다. 여기서 구간의 하한 배열은 $K \leq i \leq n$에 대해 $L_{i-K}=X_i-2v(i-K)T$, 상한 배열은 $1 \leq i \leq K$에 대해 $R_{K-i}=X_i+2v(K-i)T$라는 사실을 위 관찰에서 알 수 있었을 것이다.

 

이 문제를 $dp$를 이용하여 푼다면, $O(N^2)$에 풀 수 있음은 간단하게 알 수 있을 것이다. 여기서 $dp_{i,j}$를 $L$의 $i$번째 값과 $R$의 $j$번째 값을 가지는 구간에 도달할 수 있는지로 정의하면, $dp_{0,0}$은 참, $dp_{i,j}$가 참일 때 $L_{i+1} \leq R_j$이면 $dp_{i+1,j}$도 참, $L_i \leq R_{j+1}$이면 $dp_{i,j+1}$도 참이라는 사실을 알 수 있다. $dp_{N-K,K-1}$이 참인지만 판별하면 된다.

 

이제 위 $dp$를 행의 인덱스가 $i$, 열의 인덱스가 $j$인 표에서 한다고 생각해보자. 위 $dp$는, $L_i \leq R_j$인 점들을 모두 색칠한 후, 색칠된 칸들만 이용하여 오른쪽 또는 아래쪽으로 이동할 수 있을 때, $(0, 0)$에서 $(N-K, K-1)$로 이동할 수 있는지 판별하는 문제와 동일해진다.

우선 $L$의 최댓값이 $R$의 최댓값보다 크거나 $L$의 최솟값이 $R$의 최솟값보다 크다면 자명하게 불가능하므로, 이런 경우를 배제하자. 그러면 $L$의 최솟값이 존재하는 행과 $R$의 최댓값이 존재하는 열은 모두 색칠된 칸들일 것이다. 이 것을 색칠해보면 십자가 형태로 되는데, 우리가 구하고자 하는 경로는 항상 이 십자가를 지남은 당연하다. 때문에 문제를 $(0, 0)$에서 이 십자가로 이동할 수 있는지, 거꾸로 이동한다 생각했을 때 $(N-K, K-1)$에서 이 십자가로 이동할 수 있는지로 나눌 수 있게 된다. 두 문제는 거의 동치이므로, $(0, 0)$쪽만 풀어보자.

 

십자가 중심의 좌표를 $(l,r)$이라 하자. 여기서 재밌는 사실을 알 수 있는데, 만약 이 십자가로 이동이 가능하다면 $[0, l-1] \times [0, r-1]$의 사각형에 모두 색칠된 행이나 모두 색칠된 열이 존재한다는 것이다. 만약 $[0,l-1]$에서 최소의 $L$값을 가진 행을 $i$번째 행이라 하고 이 행이 모두 색칠되어 있지 않다고 하자. 자명하게 다른 행들에도 $i$번째 행에 색칠되지 않은 칸이 색칠되어있지 않다. 열에 대해서도 비슷하게 생각할 수 있다. 만약 모두 색칠된 행이나 열이 하나도 없다면 $(0, 0)$과 목표 지점이 단절될 수밖에 없으므로, 불가능하다. 또한 그러한 행이나 열이 하나라도 있다면, 이렇게 색칠된 행이나 열을 기준으로 다시 $(0, 0)$이 포함된 사각형 범위를 줄일 수 있고 이전과 동일한 상황이 됨을 알 수 있다. 이 과정을 반복하다가 사각형의 행 크기나 열 크기가 $1$이 되었다면 지금까지 골랐던 부분행이나 열들로 처음 언급했던 십자가로 이동할 수 있음은 자명하다. 여기서 행이나 열의 크기가 최소 1씩 줄어들기 때문에, 이 과정은 최대 $O(N)$번 반복된다. 비슷한 방법으로 $(N-K, K-1)$에서 처음 언급한 십자가로 이동할 수 있는지도 판별할 수 있다. 이 방법으로 속력 제한이 $v$일 때 가능한지 판별할 수 있고, 전체 시간복잡도 $O(N \log{X})$에 이 문제를 풀 수 있다.

 

부분 사각형에서 전체가 색칠된 행이나 열을 $O(1)$에 찾는 방법이 궁금할 수 있는데, 이는 누적 $L$값의 최대/최소, $R$값의 최대/최소와 그 위치를 전처리 하면 쉽게 찾을 수 있다. 행에 대해서만 예를 들면, 부분사각형의 $L$이 최소인 행이 $i$번째 행이라 할 때 해당 행이 전체 색칠되어있는 것과 전체 색칠된 행이 존재하는 것은 필요충분조건이다. 때문에 $L$이 최소인 행을 골라도 충분하고, 부분사각형이 $[0, l-1] \times [0, r-1]$일 때 $\displaystyle \min_{0 \leq i < l} L_i \leq \min_{0 \leq i < r} R_i$인 경우에 해당 행을 고를 수 있다. 열에 대해서도 비슷하게 $R$이 최대인 열을 고르고 $\max$값을 비교하여 판별하면 된다. $(N-K, K-1)$의 이동 가능성 판별은 반대 방향으로 $L$, $R$의 누적 최대/최소를 전처리해주면 된다. 자세한 내용은 코드를 참고하자.

굳이 그럴 이유는 없긴 하지만 세그로 해도 TLE는 안 날 것 같다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

int n, k;
ll T, X[MAX], L[MAX], R[MAX];
pll Lmx[MAX], Lmn[MAX], Rmx[MAX], Rmn[MAX];

bool chk(ll v) {
    L[0] = R[0] = X[k];
    for(int i = k - 1; i >= 1; i--) {
        R[k-i] = X[i] + 2 * v * T * (k - i);
    }
    for(int i = k + 1; i <= n; i++) {
        L[i-k] = X[i] + 2 * v * T * (k - i);
    }

    Lmx[0] = Lmn[0] = Rmx[0] = Rmn[0] = {X[k], 0};
    for(int i = k - 1; i >= 1; i--) {
        Rmx[k-i] = max(Rmx[k-i-1], {R[k-i], k - i});
        Rmn[k-i] = min(Rmn[k-i-1], {R[k-i], k - i});
    }
    for(int i = k + 1; i <= n; i++) {
        Lmx[i-k] = max(Lmx[i-k-1], {L[i-k], i - k});
        Lmn[i-k] = min(Lmn[i-k-1], {L[i-k], i - k});
    }

    if(Lmx[n-k].fi > Rmx[k-1].fi || Lmn[n-k].fi > Rmn[k-1].fi) return false;
    
    int l = Lmn[n-k].se, r = Rmx[k-1].se;
    while(l && r) {
        if(Lmn[l-1].fi <= Rmn[r-1].fi) l = Lmn[l-1].se;
        else if(Lmx[l-1].fi <= Rmx[r-1].fi) r = Rmx[r-1].se;
        else return false;
    }
    
    Lmx[n-k] = Lmn[n-k] = {L[n-k], n-k}, Rmx[k-1] = Rmn[k-1] = {R[k-1], k-1};
    for(int i = 2; i <= k; i++) {
        Rmx[k-i] = max(Rmx[k-i+1], {R[k-i], k - i});
        Rmn[k-i] = min(Rmn[k-i+1], {R[k-i], k - i});
    }
    for(int i = n - 1; i >= k; i--) {
        Lmx[i-k] = max(Lmx[i-k+1], {L[i-k], i - k});
        Lmn[i-k] = min(Lmn[i-k+1], {L[i-k], i - k});
    }

    l = Lmn[0].se, r = Rmx[0].se;
    while(l < n - k && r < k - 1) {
        if(Lmn[l+1].fi <= Rmn[r+1].fi) l = Lmn[l+1].se;
        else if(Lmx[l+1].fi <= Rmx[r+1].fi) r = Rmx[r+1].se;
        else return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> k >> T;
    for(int i = 1; i <= n; i++) {
        cin >> X[i];
    }

    ll lb = 0, ub = (INF + T - 1) / T;
    while(lb < ub) {
        ll m = lb + ub >> 1;
        if(chk(m)) ub = m;
        else lb = m + 1;
    }
    cout << lb;
}