Google Code Jam 2009 - Round1C 복습

http://code.google.com/codejam/contest/dashboard?c=189252#

A. All Your Base

기원전 2100년, 어떤 외계인이 지구에와 자신의 언어로 지구와의 전쟁까지 남은 시간을 기록했다.

이 외계인의 언어의 각 심볼은 하나의 숫자와 대응되는 것으로 보인다. 예를 들어 'ab2ac999'는 10진수로 '31536000'과 대응될지도 모른다. 하지만 불행하게도 우리는 이 외계인이 사용하는 진수와 각 심볼이 정확히 어떤 숫자와 대응되는지 알 수 없다. 그래서 우리는 외계인이 쓴 암호문이 나타낼 수 있는 최소한의 숫자를 알고 싶다.

The answer will never exceed 10¹⁸

가능한 최소의 숫자를 구하므로 base가 최소가 되야한다. base의 하한은 심볼의 갯수와 같으므로 우선 암호문에 몇개의 심볼이 나타나는지 새어야한다. 그 후 가장 먼저 나타나는 심볼 순으로 작은 숫자를 대응 시킨다. 이때 첫번째 나타나는 심볼이 1이되고 두번재가 0이되는것은 예외로 한다.
답이 10^18승 이내로 들어온다는 전제조건이 있으므로 64bit 정수형으로 답을 계산하면 된다. (누군가는 big int 구현했다지 아마.. ㅋㅋ)
#include <cstdlib> #include <cstdio> int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { char buffer[100] = {0}; scanf("%s", buffer); int digits = 0; int assign[40], digit[40] = {0}, number[100] = {0}; for (int i = 0; i < 40; i++) { assign[i] = -1; digit[i] = i; } digit[0] = 1; digit[1] = 0; for (int i = 0; buffer[i]; i++) { int ch = buffer[i]; int conv = 0; if (ch >= '0' && ch <= '9') conv = ch - '0'; else conv = ch - 'a' + 10; if (assign[conv] == -1) assign[conv] = digit[digits++]; number[i] = assign[conv]; } if (digits == 1) digits = 2; long long ans = 0; for (int i = 0; buffer[i]; i++) ans = ans * digits + number[i]; printf("Case #%d: %lld\n", t, ans); } return 0; }

 
B. Center of Mass

N마리의 개똥벌레가 있다. 이 개똥벌레들은 오로지 일정한 속도로 이동하며, 모든 개똥벌레는 같은 질량을 가진다. 당신은 우주의 중심좌표(0, 0, 0) 에 서있으며, 개똥벌레의 무게중심이 당신과 얼마나 가까워 질 수 있는지 알고싶다.

시간 t=0 일때 N마리의 개똥벌레의 위치와 속도가 주어졌을 때, 나와 개똥벌레들의 무게중심이 가장 가까워지는 시간과 그때의 무게중심과의 거리를 구하여라.

고등학교였을 때는 단번에 수식을 세워서 풀었겠지만, 지금은 식의 전계와 계산능력이 그때에 비해 턱없이 부족하므로 컴퓨터에게 일을 시키도록 하자.

시간 t에서 개똥벌레의 무게중심은 각 개똥벌레의 좌표의 x, y, z축 성분의 평균 좌표가 된다. 모든 개똥벌레가 등속도 운동을 하므로 무게중심또한 등속으로 움직이며, 이 벡터는 각 개똥벌레의 벡터의 합과 같다. 여기에서 두가지 케이스로 분기가 되는데 무게중심이 이동하는 케이스와 이동하지 않는 케이스가 있다.
무게중심이 이동하지 않는 케이스(무게중심의 이동벡터가 0)는 t=0을 대입하여 그냥 나와 무게중심사이의 거리를 구하면끗... 무게중심이 이동하는 케이스는 나와 무게중심사이의 거리가 2차방정식으로 주어지며 거리가 최소가 되는 점은 이 2차방정식이 극소가 되는 점이다. 따라서 문제를 풀려면 2차방정식을 미분하여 극소점을 구하면 된다.
하지만 계산이 귀찮으므로 터너리서치를 이용하여 간단히 문제를 풀 수 있다.
#include <cstdlib> #include <cstdio> #include <cmath> int x[501], y[501], z[501], vx[501], vy[501], vz[501]; // 거리 double distance(double time, int n) { double sx = 0, sy = 0, sz = 0; for (int i = 0; i < n; i++) { sx += x[i] + vx[i] * time; sy += y[i] + vy[i] * time; sz += z[i] + vz[i] * time; } double cx = sx / n; double cy = sy / n; double cz = sz / n; return sqrt(cx*cx + cy*cy + cz*cz); } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d%d%d%d%d", &x[i], &y[i], &z[i], &vx[i], &vy[i], &vz[i]); double time = 0; // 무게 중심이 이동하지 않는지 검사 bool stop = false; long long svx = 0, svy = 0, svz = 0; for (int i = 0; i < n; i++) { svx += vx[i]; svy += vy[i]; svz += vz[i]; } if (svx == 0 && svy == 0 && svz == 0) stop = true; // 무게 중심이 이동하는 케이스 - 터너리 서치로 찾는다 if (stop == false) { double left = 0; double right = 1e11; for (int i = 0; i < 5000; i++) { double a = (left*2 + right) / 3; double b = (left + right*2) / 3; double fa = distance(a, n); double fb = distance(b, n); if (fa > fb) left = a; else right = b; } time = (right + left) / 2; } printf("Case #%d: %.10lf %.10lf\n", t, distance(time, n), time); } return 0; } <textarea> <br /><br /> </DIV><br /> </div> <P><br />  </P><SPAN id=tx_marker_caret></SPAN>

C. Bribe the Prisoners

감옥이 있는데 이 감옥은 감방이 일렬로 배치되어 있다. 서로 인접한 감방에 수감된 죄수를 '이웃'이라 부르는데 '이웃'들 끼리는 감방의 벽을 통해 서로 커뮤티케이션을 할 수 있다. 죄수들은 평소에는 평화롭게 지내지만, 어떤 죄수가 석방되면 그 죄수의 이웃죄수는 그 사실을 알게되고 난동을 부리게 된다. 그 즉시 난동을 부리는 죄수의 이웃또한 그 사실을 알게되어 난동을 부린다. 하지만 난동을 부리는 죄수의 옆방이 비어있다면 난동을 더 이상 퍼지지 않고 거기에서 끝난다.
난동을 부리는 죄수를 진정시키기 위해 당신은 죄수에게 돈을 주어야 한다.

P개의 감방에 죄수가 가득 수감되어 있을 때, 이 중 Q명의 죄수를 석방하려 한다. 죄수에게 지불되는 돈을 최소화하기 위해 이 Q명의 죄수를 어떤순서로 석방해야 할 것인가? 당신이 지불해야할 최소의 돈을 계산하라

죄수를 석방하는 순서에 따라 지불하는 금액이 달라진다. Q명을 석방하므로 전체 경우의 수는 Q!이 되는데 라지 테스트 케이스에서 Q가 무려 100이기 때문에 Q!의 해법으로는 대화가 되지 않는다.

해법을 찾기까지 상당히 고생을 했다. 느낌상 DP라는 것은 문제를 보자마자 떠올랐지만 어떻게 공간을 정의해야 할 것인지 쉽게 떠오르지 않았다. 그러다가 결국 해법이 떠올라서 풀긴 풀었는데, 막상 해법을 알고나니 어려운 문제도 아니었다.

죄수가 A...p...B 까지 있는 경우, 이 중  죄수 p를 석방 한다고 생각해보자. 이때 p를 석방하면서 지불해야하는 돈은 B-A가 된다. 그리고 그 다음 상태는 죄수A...p-1인 상태와 p+1...B인 상태로 양분되며, 이 두 상태는 서로 독립적인 문제로 생각할 수 있으므로 각기 따로 풀어낼 수 있다. 분할정복의 마술의 고리가 여기서 발생한다.(유후~~) 그렇다면 다시 원래로 돌아가서 A ... p ... B인 상태에서 p를 석방하는 비용은 p를 석방할때 당장 발생하는 비용 B-A 와 그 다음 상태인 A...p-1의 비용과 p+1...B의 비용의 합으로 계산할 수 있다.
#include <cstdlib> #include <cstdio> #include <memory.h> inline int MIN(int a, int b) { return (a < b) ? a : b; } inline int MAX(int a, int b) { return (a > b) ? a : b; } int P, Q; int QS[101]; int mem[101][101]; int go(int l, int r, int lq, int rq) { if (lq > rq || lq < 0 || rq >= Q || l < 1 || r > P) return 0; int& res = mem[lq][rq]; if (res != -1) return res; res = 1234567890; for (int q = lq; q <= rq; q++) { res = MIN(res, go(l, QS[q]-1, lq, q-1) + go(QS[q]+1, r, q+1, rq) + (r - l)); } return res; } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { scanf("%d%d", &P, &Q); for (int i = 0; i < Q; i++) scanf("%d", &QS[i]); memset(mem, 0xFF, sizeof(mem)); printf("Case #%d: %d\n", t, go(1, P, 0, Q-1)); } return 0; }