[Medium] KingdomXCitiesandVillages
Topcoder SRM 503 Div1
expectation 의 선형성을 이용해 문제를 단순화시킬 수 있다
E( sum( 마을 i를 골랐을 때 선택된 도로의 길이 ), for all i )
= sum( E( 마을 i를 골랐을 때 선택된 도로의 길이 ) ), for all i
결국 각 마을 i에 대해 선택된 도로의 길이의 기대값을 구해서 다 더해주는 문제로 바뀌게 된다.
마을 i를 제외한 나머지 마을, 그리고 모든 city에 대해 거리를 구한 다음 오름차순으로 정렬해놓은 배열 s[] 를 만들자.
s[] 의 앞에서부터 city가 처음 등장하기 전 까지의 모든 village와 처음 등장한 city가 답을 구할 때 고려된다. 나머지는 버린다.
j번째에 위치한 village와 도로를 연결할 확률은 어떻게 될까?
이렇게 되려면 0~j-1번째 village는 마을 i가 선택된 이후에 선택되어야 하고, j번째 village는 마을 i가 선택되기 전에 선택되어야 한다.
이걸 일렬로 늘어놓고 이렇게 될 확률을 구해보면 j! / (j+2)! = 1 / (j+1)(j+2) 이다.
j번째에 위치한 city와 도로를 연결할 확률은 어떻게 될까?
이렇게 되려면 0~j-1번째 village는 마을 i가 선택된 이후에 선택되어야 한다.
마찬가지로 생각해보면 확률은 j! / (j+1)! = 1 / (j+1) 이다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cmath> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| inline double dist(int x1, int y1, int x2, int y2) { | |
| return sqrt((long long)(x1 - x2) * (x1 - x2) + (long long)(y1 - y2) * (y1 - y2)); | |
| } | |
| class KingdomXCitiesandVillages { | |
| public: | |
| double determineLength(vector<int> cityX, vector<int> cityY, vector<int> villageX, vector<int> villageY) { | |
| int n = cityX.size(), m = villageX.size(); | |
| double ans = 0; | |
| for (int i = 0; i < m; ++i) { | |
| double nearcity = 1e+30; | |
| for (int j = 0; j < n; ++j) { | |
| nearcity = min(nearcity, dist(villageX[i], villageY[i], cityX[j], cityY[j])); | |
| } | |
| vector<double> vdist(m); | |
| for (int j = 0; j < m; ++j) { | |
| vdist[j] = (i == j) ? 1e+30 : dist(villageX[i], villageY[i], villageX[j], villageY[j]); | |
| } | |
| sort(vdist.begin(), vdist.end()); | |
| for (int j = 0; j < m; ++j) { | |
| if (vdist[j] > nearcity) { | |
| ans += nearcity / (j + 1); | |
| break; | |
| } | |
| ans += vdist[j] / ((j + 1) * (j + 2)); | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |