[IOI2014 Day2] Holiday 해법

인접한 도시 사이를 이동하는데 걸리는 시간 1, 한 도시에 있는 관광지를 모두 둘러보는 시간 1이 걸리고 시작점이 주어졌을 때, 가장 관광지를 많이 방문하는 문제다. 물론 같은 관광지를 여러 번 방문해서는 안된다.

답이 될 수 있는 이동 경로는 아래 두 가지 중 하나이다.

1) 시작점에서 왼쪽으로 0칸 이상 가다가 어느 순간 오른쪽으로 이동하여, 시작점 보다 오른쪽으로 간다.

2) 시작점에서 오른쪽으로 0칸 이상 가다가 어느 순간 왼쪽으로 이동하여, 시작점 보다 왼쪽으로 간다.

즉, 쉽게 말하자면 방향을 한 번만 바꾼다는 것이다.

두 번 이상 방향을 바꾸어 왔다갔다 하는 것은 이동하는 시간만 늘리므로 항상 안좋다는 것을 알 수 있다.

2번 경우는 전체를 좌우로 뒤집었을 때 1번 경우와 같아지므로, 1번 경우에 대해서 답을 구하는 방법만 설명하겠다.

문제를 해결하기 위해서는 시작점에서 오른쪽으로만 갈 때, $t$ 시간 안에 방문하는 관광지 수의 최대값을 $0 \leq t \leq d$인 모든 $t$에 대해 계산해야한다.

편의상 시작점을 $0$번 도시라고 하자.

어떤 시간 $t$에 대해 방문하는 관광지 수의 최대값을 구하는 방법을 설명하겠다.

$0 \leq i < n$인 모든 $i$에 대해 $i$번 도시까지 이동한다고 했을 때, 방문 가능한 도시는 $t - i$개이며, 가장 관광지 수가 많은 도시들을 먼저 방문하는 것이 좋다. 이 때 방문 가능한 도시 중 관광지 수가 많은 상위 $t - i$개에 대한 합을 세그먼트 트리를 써서 $O(\lg N)$ 에 구하는 것이 가능하다. 

위 알고리즘을 모든 $t$에 대해 하면 $O(N^2 \lg N)$이 걸린다.

$p(t)$를 시간 $t$에 최대로 많은 관광지를 방문할 때 마지막으로 위치한 도시 번호라고 하자. 마지막으로 위치 가능한 도시가 여러 곳일 때, 그러한 도시들 중 가장 왼쪽에 있는 도시라고 하자.

$t_1 < t_2$일 때, $p(t_1) \leq p(t_2)$라는 것을 조금만 생각해보면 알 수 있다.

$0 \leq t \leq d$인 모든 $t$에 대해 최대값을 알아야하는데, 이는 분할정복 비슷한 방법으로 해결할 수 있다.

처음에 $m = \frac{d}{2}$인 $m$에 대해 위에서 말한 알고리즘으로 최대값을 계산하고 $p(t)$도 찾는다. 그러면 $t > m$인 $t$에 대해 위 알고리즘에서 끝 도시의 후보가 $0$번 도시부터 $n-1$번 도시까지가 아닌 $p(t)$번 도시부터 $n-1$번 도시까지로 줄어들고, 마찬가지로 $t < m$인 $t$에 대해 끝 도시의 후보가 $0$번 도시부터 $p(t)$번 도시까지로 줄어들게 된다.

이를 재귀적으로 해결하여 $0 \leq t \leq d$인 모든 $t$에 대해 최대값을 계산할 수 있다. 이 때 시간복잡도는 $O(N {\lg}^2 N)$이다.

위 방법으로 시작점에서 오른쪽으로만 갈 때 가능한 모든 시간 $t$에 대해 최대값을 구했다.

마찬가지로 시작점에서 시작점을 방문하지 않고 왼쪽으로만 갈 때 가능한 모든 시간 $t$에 대해 최대값을 구할 수 있다. 이 때 이동 시간을 1이 아니라 2로 두고 계산한다.

그러면 위에서 계산한 두 값들을 통해 시간 $d$에 대해 가능한 최대값을 계산할 수 있다.

이 처럼 시간복잡도를 줄이는 방법을 Divide & Conquer Optimization이라 한다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define MAXT 300005 typedef long long lld; static int N, S, T, K; static int A[MAXN], P[MAXN]; static lld D[MAXT], E[MAXT]; struct Z{ int a, x; } B[MAXN]; struct NODE{ int cnt; lld sum; NODE *left, *right; } container[262144], *root; NODE *new_node() { NODE *ret = &container[K++]; ret->cnt = ret->sum = 0; ret->left = ret->right = 0; return ret; } void write(NODE *now, int s, int e, int n, int v) { if (n < s || e < n) return; if (s == e){ if (v >= 0){ now->cnt = 1; now->sum = v; }else{ now->cnt = now->sum = 0; } return; } if (!now->left) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; write(now->left, s, m, n, v); write(now->right, m+1, e, n, v); now->cnt = now->left->cnt + now->right->cnt; now->sum = now->left->sum + now->right->sum; } lld get_highest(NODE *now, int s, int e, int &left) { if (left <= 0) return 0; if (now->cnt <= left){ left -= now->cnt; return now->sum; } if (s == e) return 0; int m = (s+e)>>1; lld ret = get_highest(now->left, s, m, left); if (left > 0) ret += get_highest(now->right, m+1, e, left); return ret; } void calc(int l, int r, int s, int e) { if (s > e) return; int m = (s+e)>>1, t; D[m] = -1; for (int i=l;i<=r;i++){ write(root, 1, N, P[i], A[i]); int left = m-(i-S); if (left <= 0) break; lld sum = get_highest(root, 1, N, left); if (D[m] < sum) D[m] = sum, t = i; } if (s == e) return; for (int i=l;i<=r;i++) write(root, 1, N, P[i], -1); calc(l, t, s, m-1); for (int i=l;i<t;i++) write(root, 1, N, P[i], A[i]); calc(t, r, m+1, e); } void calc2(int l, int r, int s, int e) { if (s > e) return; int m = (s+e)>>1, t; E[m] = -1; for (int i=r;i>=l;i--){ write(root, 1, N, P[i], A[i]); int left = m-(S-i)*2; if (left <= 0) break; lld sum = get_highest(root, 1, N, left); if (E[m] < sum) E[m] = sum, t = i; } if (s == e) return; for (int i=l;i<=r;i++) write(root, 1, N, P[i], -1); calc2(t, r, s, m-1); for (int i=t+1;i<=r;i++) write(root, 1, N, P[i], A[i]); calc2(l, t, m+1, e); } lld proc() { for (int i=1;i<=N;i++) B[i].a = A[i], B[i].x = i; sort(B+1, B+N+1, [](const Z &a, const Z &b){ return a.a > b.a; }); for (int i=1;i<=N;i++) P[B[i].x] = i; K = 0; root = new_node(); calc(S, N, 1, T); K = 0; root = new_node(); if (S > 1) calc2(1, S-1, 3, T); else for (int i=0;i<=T;i++) E[i] = 0; lld ret = D[T]; for (int i=1;i<=T;i++) ret = max(ret, E[i] + D[T-i]); return ret; } lld findMaxAttraction(int n, int start, int d, int arr[]) { N = n, S = start+1, T = d; for (int i=1;i<=N;i++) A[i] = arr[i-1]; lld ret = proc(); if (!start) return ret; reverse(A+1, A+N+1); S = N-S+1; return max(ret, proc()); }