두번 연속 쓰네요 굽신굽신 -.-
다른분들도 좀 써 주시죠 ㅠㅠ

• Easy ( 250 pts )

• 문제설명
  직선상에 N개의 행성들이 위치해 있다. i 번째 행성은 x[i] 좌표에 있고, m[i] 만큼의 질량을 가지고 있다. 각각의 행성들은 매우 강한 힘에 의하여 고정되어 있다. 어떤 두 행성도 같은 좌표에 있지 않다.
  이 직선 상에 고정되지 않은 위성 P가 존재한다. 이 P는 왼족에 있는 행성들이 당기는 힘과 오른족에 있는 행성들이 당기는 힘이 같은 지점에서 멈춰있다. 질량이 m1, m2인 두 물체 사이의 거리가 d일 때, 두 물체는 서로 F = G * m1 * m2 / d^2 의 힘으로 서로 잡아당기는 만유인력이 있다. (G는 양의 상수이다.)
  어떤점 P를 기준으로 만유인력의 벡터합이 0이 되는 P의 위치를 equilibrium Point라고 부른다. 달리 말하자면, P를 기준으로 왼쪽에 있는 행성들이 당기는 힘이 P를기준으로 오른쪽에 있는 행성들이 당기는 힘과 같은 점을 말한다
  N개의 점이 있을 때, N-1개의 Equilibrium Point가 존재한다고 한다. 이러한 Equilibrium Point들을 오름차순으로 정렬하여 return하시오.
  [spoiler="더 보기..."] - 문제풀이
  어렵지 않은 문제 난이도임에도 불구하고 생각보다 많은 분들이 System Test를 통과하지 못했습니다. :(
  어떤 두 점 사이의 Equilibrium Point를 찾는다고 가정하면, Binary Search를 이용하여 (항상 두 점 사이에 존재할테니까요) Eq.Point를 찾습니다. 이를 Eq.Point가 존재할 수 있는 N-1개의 구간에 대해서 찾습니다..
  하지만 대부분의 Failed System Test인 코드를 보면 Binary Search의 "종료 조건"에 문제가 있었기 때문입니다. 두 범위의 차가 1e-10 미만이 되었을 때 루프를 종료한다고 지정하는 경우라도 문제가 발생할 수 있었지요.
  예전에 한번 소개되었던 적이 있듯이, Binary Search의 경우에는 종료 조건을 구간으로 잡는것보다는, 일정 Loop만큼 수행하도록 작성하는게 효과적입니다. 100번만 루프를 돌아도, 오차는 초기값과 비교할 때, 2^-100 배가 되기 때문에 매우 작아지지요.[/spoiler]

• Medium ( 500 pts )

  • 문제 설명 당신은 파티를 열기 위해 몇 개의 케이크를 구입했다. 각 케이크의 무게는 weight[i]로 주어진다. 우선 케이크를 구입하긴 했는데 케이크의 무게가 다른 것 때문에 고민에 빠지게 되었다. 고민한 결과, 당신은 제일 무거운 케이크와 가벼운 케이크의 무게 차이를 최소화 하려고 한다. 다만, 최대 maxCut 번만 케이크를 자를 수 있다. 한 번 케이크를 다른다는 것은, 하나의 케이크를 둘로 나눈다는 뜻이며, 각 케이크 조각 무게의 합은, 자르기 전 상태의 케이크 무게와 동일하다. 물론, 한 번 자른 케이크를 다시 자르는 것도 가능하다. 당신의 목표는 최대 maxCut 번 까지 케이크를 자를 수 있다고 할 때, 제일 무거운 케이크와 제일 가벼운 케이크의 무게차를 최소화하려고 한다. 제일 좋은 방법으로 잘랐을 때, 만들어 질 수 있는 최소 차를 구하여라. [spoiler="더 보기..."] - 문제풀이 Lemma 1) 무게가 w인 케이크를 c조각으로 자른다고 할 때, 조각의 minimum weight을 최대화 하면 그 때의 제일 가벼운 케이크조각의 무게는 w/c이다.
  • 우선 c등분 하면 w/c가 나온다는 사실은 자명합니다. 또한 w' > w/c인 w'가 존재한다고 가정하면, c개의조각이 모두 w' 이상의 값이 되어야하므로, c w' > c (w/c) = w 가 되어 모순이 되지요. Lemma 2) 무게가 w인 케이크를 c조각으로 자른다고 할 때, 조각의 maximum weight을 최소화 하면 제일 무거운 케이크조각의 무게는 w/c이다.
  • Lemma 1에서와 같은 방법으로 증명할 수 있습니다. 부등호의 방향만 바꿔주면 되니까요. 자세한 증명은 생략하도록 하겠습니다. Lemma 3) 케이크가 n개 있고, i번째 케이크의 무게는 Wi, 조각수는 Ci라고 했을 때, 이 상태에서 한번 더 잘라야 한다면, Wi/Ci가 최대인 케이크를 Ci + 1조각으로 자르는 것(물론 Lemma 1, 2에서 증명한 것 처럼 i번째 케이크를 Wi/(1 + Ci)의 크기로 만든다는 뜻)이 최적의 해를 가진다.
  • Pi = Wi / Ci 라고 합시다. Lemma 1, 2에서 증명한 내용에 의하면, 각각의 케이크는 항상 등분을 하는 것이 최소값의 최대화 & 최대값의 최소화에 최적의 경우임을 알 수 있습니다. 따라서 Pi는 i번째 케이크 조각의 무게. 라고 둘 수 있습니다. 그러면 이 Pi를 정렬합시다. 정렬된 Pi를 {p1, p2, ..., pn} 라고 합시다. 여기에서 p1 <= p2 <= ... <= pn이 됩니다. Lemma 3은 여기에서 한번 더 Cut을 해야한다면 pn을 잘라야 한다는 뜻입니다. 만약 i != n인 다른 케이크에 Cut연산을 한다면, 최대조각무게와 최소조각무게의 차는 pn - min(p1, wi / (1 + ci))가 됩니다. 최대값은 유지되고 최소값만 감소하는 것이 되지요. 따라서 i != n인 케이크에 Cut연산을 하는것은 "답이 좋아질 수 없기" 때문에, pi가 제일 큰 조각을 자르는 것이 좋다고 볼 수 있겠습니다. 위의 세 가지 Lemma에 따라서, 단순한 그리디로도 해결 가능합니다. 아래의 제 소스는 O(maxCuts * n lg n)의 시간복잡도를 가지게 되지만, 사실 항상 마지막 원소의 값만 변화하기 때문에 각각의 step마다 insertion 사용하는 것이 O(maxCuts* n)으로 시간복잡도가 더 좋게 되지요. 증명에 미흡한 부분이 많으니.... ㅠㅠ 궁금한 부분은 댓글로 남겨주세요. ~~~ cpp

struct cake
{
int w, p;
cake(int _w, int _p) : w(_w), p(_p) {}
bool operator < (const cake &a) const
{
long long t1 = (long long)w * (long long)a.p;
long long t2 = (long long)p * (long long)a.w;
return t1 < t2;
}
};
struct CakesEqualization {
double fairDivision(vector weights, int maxCuts) {
vector cakes;
sort(all(weights));
double ret = weights.back() - weights.front();
for (int i = 0; i < weights.size(); ++i)
cakes.pb(cake(weights[i], 1));
for (int i = 1; i <= maxCuts; ++i)
{
cakes.back().p++;
sort(all(cakes));
ret <?= (cakes.back().w * 1.0 / cakes.back().p) -

(cakes.front().w * 1.0 / cakes.front().p);
}
return ret;
}
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
* Hard ( 1000 pts )
  아직 풀이를 모릅니다 ㅇ<-<
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/50936">원문보기</a>]</div>