[문제 보러 가기]
생각보다 높은 AC와 높은 정답률을 보여준 문제입니다. 아마도 Time Limit이 10초라는 점이 많은 작용을 하지 않았나 싶습니다. 실제 대회에서 Judge가 시간 제한에 대한 clar에 노코멘트로 일관하지 않는 이상, 시간제한을 알아보고 이에 알맞는 해법을 생각해보는 것도 중요하지 않나 생각됩니다.
maximum detour은 비교적 최근에 연구된 주제로 O(nlogn)의 해법이 존재하는것으로 알려져 있습니다. 하지만 이번 에디토리얼에선 많은 팀들이 AC를 받았다고 생각하는 O(n^2) 해법에 대해서 이야기를 해보고자 합니다.
문제를 풀기 위해 필요한 것 중 첫번째론 i번째 정점까지의 누적합을 구해놓은 테이블이 필요한데, 이는 점의 갯수만큼의 배열이 필요합니다. 점의 개수는 최대 10,000이므로 가볍게 잡힙니다 :)
그런 다음, 아래와 같이 누적합을 계산합니다. 간단한 과정이기 때문에 설명을 생략하도록 하겠습니다. 여기서 getDistance 함수는 2개의 정점 사이의 유클리드 거리를 구하는 함수입니다. 자세한 것은 마지막에 첨부된 소스코드를 참고하길 바랍니다.
[spoiler="더 보기..."]sum[0] = 0;
for(int i=1;i sum[i] = sum[i-1] + getDist(i-1,i);
}
[/spoiler]
그 다음 이를 토대로 모든 조합에 대한 D(G,vi,vj)를 계산합니다. 이는 간단한 loop와 누적합을 저장한 table을 통해 O(n^2)에 해결이 됩니다.
[spoiler="더 보기..."]double ret = -1e10;
for(int i=0;i ret >?= (sum[j]-sum[i])/getDist(i,j);
}[/spoiler]
이를 통해 완성된 소스코드는 다음과 같습니다.
[spoiler="더 보기..."]
#include
#include
int n;
double sum[10000];
int x[10000];
int y[10000];
double getDist(int i, int j) {
double dx = double(x[i] - x[j]), dy = double(y[i] - y[j]);
return sqrt(dx*dx+dy*dy);
}
int main() {
int T; scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=0;i sum[0] = 0;
for(int i=1;i sum[i] = sum[i-1] + getDist(i-1,i);
}
double ret = -1e10;
for(int i=0;i ret >?= (sum[j]-sum[i])/getDist(i,j);
}
if(ret>=1e3) {
printf("TOO LARGE\n");
}
else {
printf("%.2lf\n",ret);
}
}
}
[/spoiler]
-정현환. algospot.com 운영진