문제 설명

이 문제는 2017년 NOIP(전국정보올림피아드) 보급조 T4 문제로, 동적 프로그래밍(DP)의 데이터 구조 최적화 요구사항을 보여줍니다. 2018년 T3 및 NOI online 2020 T2 문제와 함께, NOIP 보급조가 DP 최적화에 대한 요구를 높이고 있음을 알 수 있습니다.

해결 접근법

이 문제는 시험장에서도 매우 어려운 완전 탐색 문제입니다. 주어진 데이터 범위는 다음과 같습니다: (1 \leq n \leq 500000), (1 \leq x_i \leq 10^9). (k)에서 최종 답을 직접 유도하기 어렵기 때문에, 답을 역으로 추적해야 합니다.

답의 범위를 고려할 때 이분 탐색이 적합하며, 이는 성능과 비용의 관계에서 단조성을 만족합니다. 다음 단계는 주어진 조건으로 비용을 계산하는 방법입니다.

목표 복잡도는 (O(n))입니다. 먼저 간단한 (O(n^2)) 접근법을 생각해봅시다.

(x_i)는 단조성을 가지므로 정렬이 필요 없습니다. 각 (x_i)를 노드로 간주하고, (f_i)를 첫 (i)개 노드에 대한 최적해로 정의하면, 전이 방정식은 다음과 같습니다:

[f_i = \max_{i-(d+g)\leq j \leq i-(d-g)}f_j+s_i ]

만약 (f_n \geq k)이면 조건을 만족합니다. 이 접근법으로 50점을 얻을 수 있습니다.

최적화

목표 복잡도 (O(n))를 달성하기 위해 각 상태가 단 한 번만 전이되도록 해야 합니다. 즉, (O(1)) 시간에 ([i-(d+g), i-(d-g)]) 범위 내의 (f) 최댓값을 찾아야 합니다.

이러한 최적화는 단조 큐(monotonic queue)를 사용하여 해결할 수 있습니다. 유효한 상태는 큐에 저장하고, 유효하지 않거나 불법적인 상태는 제거합니다.

최적화된 코드 예시

bool check(int g) {
    fill(f, f + n + 1, LLONG_MIN);  // 최솟값으로 초기화
    fill(q, q + n + 1, 0);
    int left_bound = max(1, d - g);  // 범위 왼쪽
    int right_bound = d + g;        // 범위 오른쪽
    front = 1;
    rear = 0;
    f[0] = 0;
    long long negative_inf = f[1];
    
    for(int i = 1, j = 0; i <= n; ++i) {
        // 현재 위치에서 범위 내인 모든 j 처리
        while(x[i] - x[j] >= left_bound && i > j) {
            if(f[j] != negative_inf) {
                // 큐에서 f[j]보다 작은 값 제거
                while(front <= rear && f[q[rear]] <= f[j]) {
                    rear--;
                }
                q[++rear] = j;
            }
            j++;
        }
        
        // 범위를 벗어난 큐 앞부분 제거
        while(front <= rear && x[i] - x[q[front]] > right_bound) {
            front++;
        }
        
        // 상태 전이
        if(front <= rear) {
            f[i] = f[q[front]] + s[i];
        }
        
        // 목표 달성 여부 확인
        if(f[i] >= k) {
            return true;
        }
    }
    return false;
}

최종 구현

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
char ch;
int sign;

// 빠른 입력 함수
template<typename T>
inline T fast_input(T &ret) {
    ret = 0;
    sign = 1;
    ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') sign = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return ret = ret * sign;
}

int n;
long long x[MAXN], s[MAXN], d, k;
long long f[MAXN], q[MAXN], front, rear;
long long total_positive = 0, max_positive = 0;

bool check(int g) {
    fill(f, f + n + 1, LLONG_MIN);
    fill(q, q + n + 1, 0);
    int left_bound = max(1, d - g);
    int right_bound = d + g;
    front = 1;
    rear = 0;
    f[0] = 0;
    long long negative_inf = f[1];
    
    for(int i = 1, j = 0; i <= n; ++i) {
        while(x[i] - x[j] >= left_bound && i > j) {
            if(f[j] != negative_inf) {
                while(front <= rear && f[q[rear]] <= f[j]) {
                    rear--;
                }
                q[++rear] = j;
            }
            j++;
        }
        
        while(front <= rear && x[i] - x[q[front]] > right_bound) {
            front++;
        }
        
        if(front <= rear) {
            f[i] = f[q[front]] + s[i];
        }
        
        if(f[i] >= k) {
            return true;
        }
    }
    return false;
}

int main() {
    fast_input(n);
    fast_input(d);
    fast_input(k);
    
    for(int i = 1; i <= n; ++i) {
        fast_input(x[i]);
        fast_input(s[i]);
        if(s[i] > 0) {
            total_positive += s[i];
        }
    }
    
    // 모든 양의 점수 합이 k보다 작으면 불가능
    if(total_positive < k) {
        printf("-1\n");
        return 0;
    }
    
    int low = 0, high = x[n], mid, result;
    while(low <= high) {
        mid = (low + high) >> 1;
        if(check(mid)) {
            high = mid - 1;
            result = mid;
        } else {
            low = mid + 1;
        }
    }
    
    printf("%d\n", result);
    return 0;
}