Google Code Jam 2009 - Round1A 복습

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

A. Multi-base happiness

숫자의 각 다지트의 제곱합을 구하여 반복, 반복 해서 결국 1이 나오면 행복한 숫자란다.
예를 들어 10진수 82는 아래와 같이 행복한 숫자임을 알 수 있다.

8*8 + 2*2       = 64 + 4    = 68,  repeat:
6*6 + 8*8       = 36 + 64   = 100, repeat:
1*1 + 0*0 + 0*0 = 1 + 0 + 0 = 1 (happy! :)

주어진 모든 base에 대해 행복한 숫자가 되는 가장 작은 수를 찾아 10진수로 출력하라.

Limits
2 ≤ all possible input bases  10

숫자 2부터 차례대로 각 base에 대해 happy가 되는지 검사를 해보는 수밖에 별다른 방법이 없다.
이때 한 번 계산 했던 결과를 또 계산하지 않도록 메모리를 잘 활용해야 하는것이 중요하다.

그렇다면 메모리를 얼마나 잡아야 하는지가 중요한데, 최악의 경우는 2, 3, 4, ... , 10 진수에서 모두 happy가 되는 숫자를 구하는 경우로 이때 답이 대략 1000만을 조금 넘게 되므로(컴퓨터로 돌려본 결과) 메모리를 여유있게 잡아서 풀면 되겠다.
#include <cstdlib> #include <cstdio> #include <string> #include <sstream> #include <map> using namespace std; const int MAX_MEM = 13000000; int N = 0; int bases[10] = {0}; int mem[11][MAX_MEM+1]; int Go(int num, int base) { if (num > MAX_MEM) printf("no"); int& res = mem[base][num]; if (res != -1) return res; res = 0; int acc = 0; while (num > 0) { int r = num % base; acc += r * r; num /= base; } if (acc == 1) return res = 1; else return res = Go(acc, base); } int main() { char buff[1024]; int T; gets(buff); T = atoi(buff); memset(mem, 0xFF, sizeof(mem)); for (int t = 1; t <= T; t++) { gets(buff); stringstream sin(buff); memset(bases, 0x00, sizeof(bases)); N = 0; int base; while (sin >> base) if (base != 2) bases[N++] = base; int ans = 1; bool no = true; while (no) { ans++; no = false; for (int i = 0; i < N; i++) { if (Go(ans, bases[i]) == 0) { no = true; break; } } } printf("Case #%d: %d\n", t, ans); } }

B. Crossing the Road

바둑판 처럼 아주 정리가 잘 된 도로가 있다. 이 시가지의 남서쪽 끝에서 걷기 시작해 도로를 횡단해 북동쪽 끝으로 이동하려고 한다. 한 블록을 인도를 따라 이동하는데는 2분이 걸리고 횡단보도를 건너는데에는 1분이 걸린다. 횡단보도를 건너기 위해서는 신호등이 파란불이 될 때까지 기다려야 하는데, 각 교차로의 신호등 주기가 아래와 같이 주어진다.

S0, W0, T0

S0는 남-북 으로 파란불이 들어왔을 때 파란불이 지속되는 시간이고 W0는 동-서로 파란불이 들어왔을 때 신호가 지속되는 시간이다. T0가 되었을 때 남-북으로 파란불이 들어오며, S0시간이 지난후 W0시간동안 동-서로 파란불이 들어온다.

그럼 목적지까지 최단 시간에 갔을때 소요되는 시간은 얼마나 걸릴 것인가

구현하기 엄청 귀찮아 보이는 문제다.
여러가지 방법으로 풀 수 있을것으로 보이는데, 우선순위 큐를 이용하여 풀었다.

문제공간상의 한 상태는 지도에서의 위치와 그 위치까지 도달하는데 걸린 시간으로 정의할 수 있다. 지도에서의 위치는 각 교차로의 네 꼭지점(북동, 북서, 남동, 남서)중 하나가 된다.

시간 t에 어느 한 위치에서 다른 위치로 이동할 수 있는 경우는 남북으로 이어진 횡단보도를 건너거나, 동서로 이어진 횡단보도를 건너거나, 인도를 따라 남북으로 이동하거나, 인도를 따라 동서로 이동하거나 이 넷 중 하나이다.
인도를 따라 이동하는 것은 시간 t에서 지체없이 이동할 수 있으며 다음 장소로 이동하는데 2분이 소요된다. 횡단보도를 건널때에는 현재 위치한 교차로에서 신호등의 주기를 계산하여 다음 위치로 이동하는데 걸리는 시간을 계산할 수 있다.

우선순위큐는 min-heap으로 구성하여 도달한 시간이 가장 빠른 상태를 pop하여 다음 4개의 상태를 계산하여 push한다. 우선순위큐에서 한 상태를 pop했는데 이 위치에 대한 처리가 이미 되었다면, 지금 pop한 상태는 이 위치에 가장 빨리 올 수 있는 경우가 아니므로 그냥 버리고 다음 상태를 pop한다.

처음 상태의 위치는 남서쪽 끝에있는 교차로의 남서방향의 꼭지점이며 시간은 0이며, 북동쪽 끝에 처음으로 도달한 시간이 우리가 구하는 해가 된다.
#include <cstdlib> #include <cstdio> #include <queue> using namespace std; int N, M; struct INTER { INTER() { s = w = t = 0; } INTER(int _s, int _w, int _t) { s = _s; w = _w; t = _t; } int s; int w; int t; }; INTER Inters[21][21]; int Corners[41][41]; int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { scanf("%d%d", &N, &M); memset(Corners, 0xFF, sizeof(Corners)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d%d%d", &Inters[i][j].s, &Inters[i][j].w, &Inters[i][j].t); } } priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > que; // first location que.push(make_pair(0, make_pair(N*2-1, 0))); int ans = 0; while (!que.empty()) { // earliest state pair<int, pair<int, int> > state = que.top(); que.pop(); // state int time = state.first; int y = state.second.first; int x = state.second.second; // end point if (y == 0 && x == M*2-1) { ans = time; break; } // corner if (y < 0 || y >= N*2 || x < 0 || x >= M*2) continue; if (Corners[y][x] != -1 && Corners[y][x] <= time) continue; Corners[y][x] = time; // intersection int inter_y = y / 2; int inter_x = x / 2; INTER* inter = &Inters[inter_y][inter_x]; // cross time int cycle = inter->s + inter->w; int offset = 0; if (time >= inter->t) offset = (time - inter->t) % cycle; else offset = cycle - ((inter->t - time) % cycle); if (offset == cycle) offset = 0; int sn_cross = 0; int we_cross = 0; if (offset < inter->s) { sn_cross = time; we_cross = time - offset + inter->s; } else { sn_cross = time - offset + cycle; we_cross = time; } bool south = false; bool east = false; if (y & 1) south = true; if (x & 1) east = true; // from south of intersection if (south == true) { // go south que.push(make_pair(time + 2, make_pair(y+1, x))); // go north que.push(make_pair(sn_cross + 1, make_pair(y-1, x))); } // from north of intersection else { // go south que.push(make_pair(sn_cross + 1, make_pair(y+1, x))); // go north que.push(make_pair(time + 2, make_pair(y-1, x))); } // from west of intersection if (east == false) { // go west que.push(make_pair(time + 2, make_pair(y, x-1))); // go east que.push(make_pair(we_cross + 1, make_pair(y ,x+1))); } // from east of intersection else { // go west que.push(make_pair(we_cross + 1, make_pair(y, x-1))); // go east que.push(make_pair(time + 2, make_pair(y ,x+1))); } } printf("Case #%d: %d\n", t, ans); } return 0; }

C. Collectiong Cards

유희왕 카드를 하는데 모든 종류의 카드를 다 모으고 싶다.
카드를 모으기 위해서는 카드세트를 사야하는데 카드세트에는 서로 다른 N종류의 카드가 무작위로 들어가 있다. 유희왕에 총 C가지의 카드가 있는 경우 모든 카드를 다 모으기 위해서는 카드세트를 몇 번이나 사야할까?
평균 기대치를 오차범위 10^-5 이내로 구해보자

머리가 지끈거리는 확률문제인데, 이런 문제일수록 마음을 차분히 가다음고 차근차근 풀어나가는게 중요한 것 같다.

C개의 카드중 K개의 카드를 가지고 있는 상태를 가정하자.
새로 카드세트를 사서 N개의 카드가 나왔는데, 이중 a개가 이미 가지고 있는 카드이고 b개가 새로 추가된 카드가 되는 경우는 KCa * C-KCb  이다. (a + b = N)

새로 N개의 카드가 들어있는 카드세트를 사서 내가 가진 카드의 갯수가 q개가 되는 경우는

원래 q개를 가지고 있었고 새로 산  N개의 카드가 모두 원래 내가 가지고 있는 카드이다.
원래 q-1개를 가지고 있었고 새로 산 N개의 카드 중 1개만 원래 내가 가지고 있지 않던 카드이다.
원래 q-2개를 가지고 있었고 새로 산 N개의 카드 중 2개만 원래 내가 가지고 있지 않던 카드이다.
...
원래 q-N개를 가지고 있었고 새로 산 N개의 카드가 모두 내가 가지고 있지 않던 카드이다.

이렇게 요약할 수 있다.


그럼 확률은 새로 카스세트를 사서 내가 가진 카드의 갯수가 q개가 될 확률 Pq는

Pq = P'q * qCN * C-qC0 / CCN
     + P'q-1 * q-1CN-1 * C-(q-1)C1 / CCN
     + P'q-2 * q-2CN-2 * C-(q-2)C2 / CCN
     ...
     + P'q-N * q-NC0 * C-(q-N)CN / CCN

이런 점화식으로 나타낼 수 있다.

카드를 T번 샀을 때 PN을 구해 T*PN을 모두 더하면 우리가 원하는 답이 된다. 오차범위내에 답이 들어가야 하므로 T를 충분히 크게하여 답을 구하자
#include <cstdlib> #include <cstdio> #include <memory.h> int main() { double com[41][41] = {0}; double mem[2][41] = {0}; com[0][0] = 1; for (int i = 1; i <= 40; i++) { com[i][0] = 1; for (int j = 1; j <= i; j++) { com[i][j] = com[i-1][j-1] + com[i-1][j]; } } int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { int N, C; scanf("%d%d", &C, &N); int cur = 1; int pre = 0; double ans = 0; mem[0][0] = 1; for (int it = 1; it <= 100000; it++) { for (int i = 0; i <= C; i++) { mem[cur][i] = 0; for (int j = 0; j <= N && j <= i; j++) { mem[cur][i] += mem[pre][i-j] * com[i-j][N-j] * com[C-(i-j)][j] / com[C][N]; } } ans += it * mem[cur][C]; mem[cur][C] = 0; cur = 1- cur; pre = 1- pre; } printf("Case #%d: %.10lf\n", t, ans); } return 0; }