TopCoder SRM 421

http://www.topcoder.com/stat?c=round_overview&er=5&rd=13512

자정에 Single Round Match 421이 있었습니다.

오늘은 250에 수치해석문제와 500에 약간 생각하기 어려운 그리디 문제가 출제되었고 그리고 1000엔 무슨 문제인지 모르겠네요^^
항상 double형을 처리하는 문제가 나오면 그 오차때문에 틀리는 코더가 많은데 오늘도 역시 250에서 많은 사람들이 System Fail로 죽었습니다. 저는 뉴턴메소드가 오차범위내로 수렴하지 않아 TLE로 죽은듯합니다. ㅠㅠ

250 - EquilibriumPoints

질량을 가진 n개의 물질이 일직선상 고정되에 있습니다. 각각의 물질의 질량이 주어졌을 때 정확히 n-1개의 지점에서 중력장의 힘이 0이 된다고 함니다. 중력이 0이되는 n-1개의 지점을 찾아 오름차순으로 정렬하여 리턴하는 것이 문제입니다. 1e-9이내의 오차는 맞은것으로 간주합니다.
두 질량 사이의 중력 g는 g=G*m1*m2/d^2 으로 구할 수 있습니다.

Solving

잘 생각해 보면 일련의 물질이 있다고 했을 때 인접한 두 개의 물질 a, b를 고른다면 두 물질 사이에는 중력이 0이 되는 지점이 반드시 하나 존재한다는 것을 알 수 있습니다.

이제 두 점 사이에 중력이 0이 되는 지점을 찾아야 하는데, 방정식을 세우기가 여간 까다롭지 않습니다. 일단 오차내로 지점을 구하면 되고 두 점 사이에 반드시 해가 존재한다는 것을 알기 때문에 각 지점에 대해서 뉴턴메소드를 적용하여 문제를 풀 수 있습니다.

바이너리서치를 언제까지 반복해야하느냐가 또 다른 이슈가 될 수 있는데, High와 low의 차이가 오차범위 내로 들어올 때 까지 반복해도 되겠으나 값이 수렴이 되지 않는 경우가 있을 수가 있습니다. 이런 경우 적당히 큰 수 만큼만 반복을 해주어도 2^-n으로 오차범위가 줄어들기 때문에 수렴하지 않고 무한루프를 도는 것을 막고 정확도도 확보합니다.

#include <vector> using namespace std; class EquilibriumPoints { public: vector<double> getPoints(vector<int> x, vector<int> m) { int i,j,k; vector<double> res; for (i = 0; i < x.size()-1; i++) { double L = x[i]; double H = x[i+1]; double T = (L+H)/2; for (j = 0; j < 500; j++) { double G1 = 0, G2 = 0; for (k = 0; k <= i; k++) G1 += m[k]/((T-x[k])*(T-x[k])); for (k = i+1; k < x.size(); k++) G2 += m[k]/((T-x[k])*(T-x[k])); if (G1 > G2) L = T; else H = T; T = (L+H)/2; } res.push_back(T); } return res; } };

500 - CakesEqualization

n개의 케익의 무게가 주어집니다. 이 케익을 최대 maxCuts번 만큼 잘라 젤 무거운 케익의 무게와 젤 가벼운 케익의 무게가 최소가 되게 하고 싶습니다. n개의 케익의 무게들과 maxCuts가 주어졌을 때 최소의 무게차를 구하십시오.

1 <= n <= 50
1 <= 무게 <= 1000000000
1 <= maxCuts <= 100000

Solving

어떤 케익을 k번 자른다고 가정했을 때, 예를 들어 무게 6의 케익을 두 번 자른다고 했을 때, (2,2,2)가 되게 자를 수 있는 반면 (1,2,3)과 같이 서로 무게가 다르게 자를 수도 있습니다. 문제에선 커딩 후 젤 무거은 케익과 젤 가벼운 케익의 차이가 최소가 되기를 원합니다. a < b 인 두 개의 케익이 있다고 했을 때 b를 잘라 b1 < b2를 만든다고 가정을 합시다. 만약 b를 동등하게 자랐다면 b3, b3가 생겼다고 하면, b1 < b3 < b2의 부등식이 성립합니다. 이제 a와 비교를 하면 가능한 모든 경우는 다음과 같습니다.

(a <= b1 < b3 < b2) -> (b3-a) < (b2-a)
(b1 < a <= b3 < b2) -> (b3-a) < (b2-b1)
(b1 < b3 <= a < b2) -> (a-b3) < (b2-b1)
(b1 < b3 < b2 <= a) -> (a-b3) < (a-b1)

위에서 보는바와 같이 무거운 케익을 나눌 때 무게를 다르게 나누는 것보다 무게를 동일하게 나누는 것이 항상 유리함을 알 수 있습니다. 따라서 케익을 나눌 때는 항상 동일하게 나누도록 합니다.

케익을 한 번 나눌 수 있다고 생각하면, 당연히 가장 무거운 케익을 둘로 나누게 됩니다.
케익을 한 번 더 나눌 수 있다고 생각하면, 케익을 한 번 나누고 난 후 가장 무거운 케익을 한 번 더 나누게 됩니다.
이런식으로 계속 반복하여 최대와 최소의 무게차가 최소가 되는 경우를 찾으면 됩니다.

위의 그리디적인 방법이 나름 확신이 서기는 하지만 증명은 못하겠네요.. ^^

#include <vector> #include <algorithm> using namespace std; class CakesEqualization { public: double fairDivision(vector<int> weights, int maxCuts) { int i, j; int n = weights.size(); vector<pair<pair<double, double>, int> > prog(n); for (i = 0; i < n; i++) { prog[i].first.first = prog[i].first.second = weights[i]; prog[i].second = 1; } double minDist = 1000000000; for (i = 0; i <= maxCuts; i++) { sort(prog.begin(), prog.end()); double dist = prog[n-1].first.first - prog[0].first.first; if (dist < minDist) minDist = dist; prog[n-1].first.first = prog[n-1].first.second / (++prog[n-1].second); } return minDist; } };