[IOI2014 Day1] Rail 해법

우선, 이 문제에 대해 본격적으로 설명하기에 앞서 이 문제에서 특성을 몇 가지 설명하겠다.

1. $d(i,j)$를 정류장 $i$와 정류장 $j$ 사이의 거리라고 할 때, $d(i,j) = d(j,i)$ 이다.
2. 맨 왼쪽 정류장은 C type 이다.
3. 맨 오른쪽 정류장은 D type 이다.

$i > 0$인 $i$에 대하여 $d(0,i)$ 를 모두 구한다. 이 때 $d(0,i)$가 최소가 되는 $i$를 $x$라 하자. 이 때 정류장 $x$는 정류장 $0$ 보다 오른쪽에 있으면서 가장 가까운 D type 정류장이다.

만약 $d(0,i) = d(0,x)+d(x,i)$ 라면 정류장 $i$는 정류장 $x$ 보다 왼쪽에 있다. 이 문제를 해결하기 위해, 정류장 $x$를 기준으로 왼쪽에 있는 것과 오른쪽에 있는 것들을 나눠 따로 계산할 것이다.

왼쪽 부분과 오른쪽 부분을 계산하는 방법은 크게 차이가 없으므로, 오른쪽 부분을 구하는 방법에 대해서만 설명하겠다.

이제 정류장 $x$를 포함하여 오른쪽에 있는 정류장들만 존재한다고 생각하고 그것들의 위치와 종류를 구해야한다.

우선 정류장들을 정류장 $0$과의 거리 순서대로 정렬하여 그 순서대로 처리한다.

현재 정류장 $i$의 종류를 구하는 과정 중이라고 생각하자. 정류장 $i$가 C type이기 위한 필요충분조건은 현재까지 구한 D type 정류장 중 $d(0,i) = d(0,j)+d(i,j)$를 만족하는 정류장 $j$가 존재하는 것이다. 여기서, $d(i,j)$를 쿼리로 물어보지 않고 조건을 만족하는지 확인할 수 있다. 마지막으로 구한 D type 정류장을 $k$라고 하자. $d(i,k)$를 쿼리로 물어보고 $d(i,j)=d(i,k)-(L[k]-L[j])$ 라고 가정하여 $d(i,j)$를 매번 물어보지 않아도 된다. (여기서, L은 정류장의 위치를 나타내는 배열). 하나의 위치에 정류장이 하나 밖에 없는 조건 때문에 이러한 가정이 성립한다. 이에 대한 자세한 설명은 생략하겠다.

정류장 $i$의 종류를 결정했다면, 위치를 계산하는 것은 어렵지 않다.

$d(0,i)$를 계산하는 것에서 $N-1$번의 호출을 하고,

$d(x,i)$를 계산하는 것에서 $N-1$번의 호출을 하고,

정류장 $i$의 종류를 결정할 때, $d(i,k)$를 물어보므로, 최대 $N-2$번의 호출을 한다. 따라서, $3(N-1)$번 보다 적게 호출하므로 만점을 받을 수 있다.

시간복잡도는 $O(N^2)$ 이다. 이분 검색을 통하여 $O(N lg N)$에도 해결 가능하다.

#include "rail.h" #include <vector> #include <algorithm> using namespace std; #define MAXN 5000 #define pb push_back #define mp make_pair #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef pair<int,int> pii; static int N; static int D[MAXN],E[MAXN]; static bool left[MAXN]; static vector <pii> A; static vector <int> B; // D[i] = d(0,i) // E[i] = d(x,i) void findLocation(int n,int first,int location[],int stype[]) { int i,j,x; N = n; location[0] = first, stype[0] = 1; for (i=1;i<N;i++) D[i] = getDistance(0,i); for (x=1,i=2;i<N;i++) if (D[x] > D[i]) x = i; location[x] = first+D[x]; stype[x] = 2; for (i=0;i<N;i++) if (i != x){ E[i] = getDistance(x,i); if (i && D[i] == D[x]+E[i]){ // left by x left[i] = 1; }else if (i){ A.pb(mp(D[i],i)); } } sort(all(A)); B.pb(x); for (i=0;i<sz(A);i++){ int last = *(--B.end()), t = A[i].second; int d = getDistance(last,t); for (j=0;j<sz(B);j++){ if (D[t] == D[B[j]]+d-(location[last]-location[B[j]])){ stype[t] = 1; location[t] = location[B[j]]-d+(location[last]-location[B[j]]); break; } } if (j < sz(B)) continue; stype[t] = 2; location[t] = first+D[t]; B.pb(t); } A.clear(); B.clear(); for (i=0;i<N;i++) if (i != x){ if (!i || left[i]){ A.pb(mp(E[i],i)); } } sort(all(A)); for (i=0;i<sz(A);i++){ int t = A[i].second; if (E[t] <= E[0]){ stype[t] = 1; location[t] = location[x]-E[t]; B.pb(t); continue; } int last = *(--B.end()); int d = getDistance(last,t); for (j=0;j<sz(B);j++){ if (E[t] == E[B[j]]+d-(location[B[j]]-location[last])){ stype[t] = 2; location[t] = location[B[j]]+d-(location[B[j]]-location[last]); break; } } if (j < sz(B)) continue; stype[t] = 1; location[t] = location[x]-E[t]; B.pb(t); } }