문제 개요
NOIP 2012 심화 그룹의 '차량 여행' 문제는 두 운전자 A와 B가 번갈아 가며 동쪽(도시 번호가 증가하는 방향)으로 이동할 때의 경로를 시뮬레이션하고 최적의 출발지를 찾는 문제입니다.
- 운전 규칙: A가 먼저 운전하고 B가 다음에 운전하는 방식으로 번갈아 진행합니다.
- 도시 선택 기준:
- 운전자 B: 현재 도시와 해발 고도 차이의 절댓값이 가장 작은 도시를 선택합니다.
- 운전자 A: 현재 도시와 해발 고도 차이의 절댓값이 두 번째로 작은 도시를 선택합니다.
- 고도 차이가 동일할 경우 해발 고도가 더 낮은 도시를 우선합니다.
- 쿼리 1: 총 이동 거리 제한 $x_0$가 주어졌을 때, A의 이동 거리와 B의 이동 거리 비율이 최소가 되는 출발 도시를 찾습니다. (비율이 동일하면 해발 고도가 가장 높은 도시 선택, B의 이동 거리가 0이면 비율은 무한대로 간주)
- 쿼리 2: 임의의 출발 도시 $s_i$와 거리 제한 $x_i$에 대해 A와 B가 각각 이동한 총 거리를 구합니다.
접근 방식 및 최적화
1. 다음 목적지 사전 계산 (양방향 연결 리스트 활용)
매번 이동할 때마다 조건에 맞는 다음 도시를 탐색하면 시간 복잡도가 $O(N)$이 되어 전체 시뮬레이션 시 $O(M \cdot N^2)$의 복잡도가 발생하여 시간 초과가 납니다. 이를 해결하기 위해 각 도시에서 A와 B가 이동할 다음 도시를 사전에 계산해야 합니다.
일반적으로 std::set을 사용하여 $O(N \log N)$에 처리할 수 있지만, 상수 최적화를 위해 양방향 연결 리스트(Doubly Linked List)를 활용합니다.
- 모든 도시를 해발 고도를 기준으로 정렬하고 양방향 연결 리스트로 연결합니다.
- 출발 도시 번호 $i$를 1부터 $N$까지 순회합니다.
- 현재 도시 $i$를 연결 리스트에서 제거합니다. (이렇게 하면 리스트에는 항상 $i$보다 큰 번호를 가진 동쪽 도시들만 남게 됩니다.)
- 리스트에서 현재 도시가 있던 위치의 앞뒤로 최대 2개씩(총 최대 4개)의 후보 도시를 가져옵니다.
- 후보 도시들을 문제의 조건(고도 차이, 고도 순)에 따라 정렬하여 B의 목적지와 A의 목적지를 결정합니다.
이 방식을 사용하면 정렬 $O(N \log N)$과 리스트 순회 $O(N)$으로 매우 효율적으로 전처리가 가능합니다.
2. 이진 리프팅(Binary Lifting)을 통한 쿼리 최적화
사전에 다음 목적지를 구했더라도, 거리 제한이 클 경우 여전히 시뮬레이션에 $O(N)$의 시간이 소요됩니다. 이를 $O(\log N)$으로 줄이기 위해 이진 리프팅(倍增 DP)을 사용합니다.
상태 정의:
jump[k][i][p]: 도시 $i$에서 출발하여 현재 운전자 $p$ ($0=A, 1=B$)가 운전할 때, $2^k$번의 개별 운전 후 도달하는 도시.da[k][i][p]: 위 과정에서 운전자 A가 이동한 총 거리.db[k][i][p]: 위 과정에서 운전자 B가 이동한 총 거리.
상태 전이 (k > 0):
$2^{k-1}$번 운전한 후의 중간 지점을 mid라고 할 때, 남은 $2^{k-1}$번의 운전을 이어서 수행합니다. 이때 $2^{k-1}$이 짝수($k > 1$)이면 다음 구간의 첫 운전자는 $p$로 유지되고, 홀수($k = 1$)이면 $p \oplus 1$로 교대됩니다.
int mid = jump[k-1][i][p];
int next_p = (k == 1) ? (p ^ 1) : p;
jump[k][i][p] = jump[k-1][mid][next_p];
da[k][i][p] = da[k-1][i][p] + da[k-1][mid][next_p];
db[k][i][p] = db[k-1][i][p] + db[k-1][mid][next_p];
전체 소스 코드
아래는 양방향 연결 리스트와 이진 리프팅을 적용하여 재구성된 C++ 해결 코드입니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct City {
long long altitude;
int id;
};
int n, m;
long long max_dist;
vector<City> cities;
vector<int> pos_in_sorted;
vector<int> prev_node, next_node;
vector<int> nxtA, nxtB;
vector<long long> distA, distB;
vector<long long> original_alt;
const int MAX_LOG = 20;
vector<vector<vector<int>>> jump;
vector<vector<vector<long long>>> da, db;
void preprocess() {
cities.resize(n + 1);
original_alt.resize(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> cities[i].altitude;
cities[i].id = i;
original_alt[i] = cities[i].altitude;
}
sort(cities.begin() + 1, cities.end(), [](const City& a, const City& b) {
return a.altitude < b.altitude;
});
pos_in_sorted.resize(n + 1);
prev_node.resize(n + 1, -1);
next_node.resize(n + 1, -1);
for (int i = 1; i <= n; ++i) {
pos_in_sorted[cities[i].id] = i;
if (i > 1) prev_node[i] = i - 1;
if (i < n) next_node[i] = i + 1;
}
nxtA.resize(n + 1, -1);
nxtB.resize(n + 1, -1);
distA.resize(n + 1, 0);
distB.resize(n + 1, 0);
for (int i = 1; i <= n; ++i) {
int u = pos_in_sorted[i];
int p = prev_node[u];
int nx = next_node[u];
if (p != -1) next_node[p] = nx;
if (nx != -1) prev_node[nx] = p;
vector<int> candidates;
int curr = nx;
for (int step = 0; step < 2 && curr != -1; ++step) {
candidates.push_back(cities[curr].id);
curr = next_node[curr];
}
curr = p;
for (int step = 0; step < 2 && curr != -1; ++step) {
candidates.push_back(cities[curr].id);
curr = prev_node[curr];
}
sort(candidates.begin(), candidates.end(), [&](int a, int b) {
long long diffA = abs(original_alt[a] - original_alt[i]);
long long diffB = abs(original_alt[b] - original_alt[i]);
if (diffA != diffB) return diffA < diffB;
return original_alt[a] < original_alt[b];
});
if (candidates.size() >= 1) {
nxtB[i] = candidates[0];
distB[i] = abs(original_alt[nxtB[i]] - original_alt[i]);
}
if (candidates.size() >= 2) {
nxtA[i] = candidates[1];
distA[i] = abs(original_alt[nxtA[i]] - original_alt[i]);
}
}
}
void build_lifting() {
jump.assign(MAX_LOG, vector<vector<int>>(n + 1, vector<int>(2, -1)));
da.assign(MAX_LOG, vector<vector<long long>>(n + 1, vector<long long>(2, 0)));
db.assign(MAX_LOG, vector<vector<long long>>(n + 1, vector<long long>(2, 0)));
for (int i = 1; i <= n; ++i) {
jump[0][i][0] = nxtA[i];
da[0][i][0] = distA[i];
db[0][i][0] = 0;
jump[0][i][1] = nxtB[i];
da[0][i][1] = 0;
db[0][i][1] = distB[i];
}
for (int k = 1; k < MAX_LOG; ++k) {
for (int i = 1; i <= n; ++i) {
for (int p = 0; p < 2; ++p) {
int mid = jump[k-1][i][p];
if (mid == -1) continue;
int next_p = (k == 1) ? (p ^ 1) : p;
jump[k][i][p] = jump[k-1][mid][next_p];
da[k][i][p] = da[k-1][i][p] + da[k-1][mid][next_p];
db[k][i][p] = db[k-1][i][p] + db[k-1][mid][next_p];
}
}
}
}
pair<long long, long long> query(int start, long long limit) {
long long resA = 0, resB = 0;
int curr = start;
int p = 0;
for (int k = MAX_LOG - 1; k >= 0; --k) {
if (jump[k][curr][p] != -1 && da[k][curr][p] + db[k][curr][p] <= limit) {
limit -= (da[k][curr][p] + db[k][curr][p]);
resA += da[k][curr][p];
resB += db[k][curr][p];
curr = jump[k][curr][p];
if (k == 0) p ^= 1;
}
}
return {resA, resB};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
preprocess();
build_lifting();
cin >> max_dist;
double min_ratio = 1e18;
int best_start = 1;
for (int i = 1; i <= n; ++i) {
auto [dA, dB] = query(i, max_dist);
double ratio = (dB == 0) ? 1e18 : (double)dA / dB;
if (ratio < min_ratio) {
min_ratio = ratio;
best_start = i;
} else if (ratio == min_ratio && original_alt[i] > original_alt[best_start]) {
best_start = i;
}
}
cout << best_start << "\n";
cin >> m;
for (int i = 0; i < m; ++i) {
int s;
long long x;
cin >> s >> x;
auto [dA, dB] = query(s, x);
cout << dA << " " << dB << "\n";
}
return 0;
}