Google Code Jam 2009 - Round1B 복습

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

A.Decision Tree

Decision Tree가 아래의 포맷으로 주어진다.

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

좀 더 문법적으로 설명하면 주어지는 Tree는 아래의 정규식 문법을 따른다

tree ::= (weight [feature tree tree])
weight is a real number between 0 and 1, inclusive
feature is a string of 1 or more lower case English letters

이 Decision Tree는 어떤 동물이 얼마나 귀여운지를 판단하는 트리이다. 

트리의 노드는 '(' 와 ')' 로 둘러쌓여있다. 각 노드는 0과 1사이의 가중치를 가지며 속성을 가질 수 있다. 노드가 속성을 가지는 두 개의 child node를 가진다.

어떤 동물의 귀여운 정도를 구하는 방법은 간단하다. 우선 귀여운 정도 = 1.0 으로 루트노드로 부터 시작한다. 동물의 귀여운 정도는 만나는 노드의 가중치와 곱해진다. 만약 동물의 속성과 노드의 속성이 일치하면 그 노드의 왼쪽 자식 노드로 분기하며 그렇지 않은 경우 오른쪽으로 분기한다. 더 이상 분기할 자식노드가 없을 때 귀여운 정도가 그 동물의 귀염성을 나타낸다.

예를 들어 위 decision tree에서 furry와 freshwater 라는 속성을 가지는 동물은 귀염성은, 우선 루트노드에서 귀염성=1.0 으로 시작한다. 루트노드의 가중치가 0.2 이므로 이 동물의 귀염성은 0.2가 된다. 루트노드의 속성인 furry와 이 동물의 속성이 일치하므로 왼쪽 자식으로 분기한다. 이 노드의 가중치가 0.81이므로 이 동물의 귀염성은 0.2 * 0.81 =  0.162 가 된다. 이 노드의 속성 fast와 이 동물의 속성이 일치하지 않으므로 오른쪽으로 분기한다. 이 노드의 가중치는 0.2이므로 최종적으로 이 동물의 귀염성은 0.0324가 된다.

인풋으로 결정트리와 동물의 속성이 주어지면 이 동물의 귀염성을 계산하라.

문제자체는 크게 어렵지 않다.
인풋을 분석하여 트리를 구성하고 결정트리 법칙에 따라 동물의 귀염성을 계산하면 끝이다. 그런데 인풋이 정말 형편없게 주어지므로 파싱하는데 꽤 귀찮음이 많이 느껴졌다.

이런 귀찮은 코드를 좀 더 빠르고 간결하게 작성할 수 있는 훈련이 더 필요한 것 같다.
#include <cstdlib> #include <cstdio> #include <string> #include <vector> #include <sstream> using namespace std; struct TNode { TNode() { weight = 0; feature = ""; left = right = parent = 0; } double weight; string feature; TNode* left; TNode* right; TNode* parent; }; TNode* MakeTree(string& expr, int& index, TNode* parent) { TNode* node = new TNode; node->parent = parent; // open token while (expr[index++] != '('); // weight node->weight = atof(&expr[index]); // next token while (!(expr[index] >= 'a' && expr[index] <= 'z') && expr[index] != ')') index++; // leaf if (expr[index] == ')') { index++; } // has feature & childs else { // feature //while (expr[index] != ' ') index++; node->feature = &expr[index]; if (node->feature.find(' ')) node->feature.erase(node->feature.find(' ')); while (expr[index] != '(') index++; // left child node->left = MakeTree(expr, index, node); // right child node->right = MakeTree(expr, index, node); // close token while (expr[index] != ')') index++; index++; } return node; } double Go(TNode* node, vector<string>& features, double p) { p *= node->weight; if (node->left != 0) { bool match = false; for (int i = 0; i < (int)features.size(); i++) { if (features[i] == node->feature){ match = true; break; } } if (match) p = Go(node->left, features, p); else p = Go(node->right, features, p); } return p; } int main() { char buffer[1024]; gets(buffer); int T = atoi(buffer); for (int t = 1; t <= T; t++) { printf("Case #%d:\n", t); gets(buffer); int L = atoi(buffer); string expr; for (int i = 0; i < L; i++) { gets(buffer); expr += buffer; expr += " "; } int index = 0; TNode* root = MakeTree(expr, index, 0); gets(buffer); int A = atoi(buffer); for (int i = 0; i < A; i++) { gets(buffer); stringstream sin(buffer); string name; sin >> name; int n; sin >> n; vector<string> features; for (int j = 0; j < n; j++) { string feature; sin >> feature; features.push_back(feature); } printf("%.10lf\n", Go(root, features, 1.0)); } } return 0; }

B. The Next Number

1에서 9까지의 디지트를 각각 Di개(1 <= i <= 9) 를 갖는 숫자의 리스트가 있다. 예를 들어 115, 151, 511, 1015, 1051, ... 은 모두 '1'을 두 개, '5'를 한 개 가진 숫자의 리스트의 원소이다.

어떤 숫자 N이 주어졌을 때, 이 숫자가 속한 리스트에서 N다음에 오는 숫자를 구하여라.

문제도 짧고 간결하고, 인풋과 아웃풋도 간결하고, 무엇보다 풀이도 간결하다.

주어지는 숫자 N을 문자열로 생각하면 리스트에서 N다음에 나오는 숫자는 N의 다음 다음 순열이라는 것을 알 수 있다. 그런데 N이 내림차순으로 정렬된 문자열이라면 (54421100 같은..) 다음 순열이 N 다음에 오는 숫자가 되지 않는다. (00112445) 이 경우에만 따로 처리를 해서 적당히 0을 추가하여 처리하면 되겠다.
#include <cstdlib> #include <cstdio> #include <string> #include <algorithm> #include <iostream> using namespace std; int main() { int T; cin >> T; for (int t = 1; t <= T; t++) { string num; cin >> num; if (next_permutation(num.begin(), num.end())) { printf("Case #%d: %s\n", t, num.c_str()); } else { int a = 0; while (num[0] == '0') swap(num[0], num[a++]); num = num.substr(0, 1) + "0" + num.substr(1); printf("Case #%d: %s\n", t, num.c_str()); } } return 0; }

C. Square Math

아래와 같은 W*W 크기의 보드가 주어진다.

2+3
+4-
1+0

보드의 각 칸은 한자리의 숫자이거나 + 혹은 - 이다.

이 보드의 숫자칸 중 아무자리에서나 시작해서 상하좌우 4방향 중 한 방향으로 아무렇게나 이동하여 식을 써 나간다. 예를 들어 위 그림에서 첫번째 칸에서 시작하여 오른쪽으로 두칸 간 뒤 아래로 한 칸 가고 왼쪽으로 한 칸 가면, 식 '2+3-4'가 완성된다.

보드와 숫자 Q가 주어졌을 때, 보드위에서 이런식으로 이동하여 얻을 수 있는 식의 계산 결과가 Q와 일치하는 식을 구하여라. 만약 답이 여러개 존재하면 그 중 가장 짧은 식을 구하여라. 이 마저도 여러개가 존재하면, 사전순으로 가장 앞서는 식을 구하여라.

Large dataset

2 ≤ W ≤ 20
1 ≤ Q ≤ 50
1 ≤ each query ≤ 250

Large Test의 입력크기가 별로 크지 않으면서 은근히 커서 푸는데 꽤나 고생했다.
사전순으로 가장 앞서는 식을 구하는 것도 만만치가 않아서 오늘 오후내내 이 문제가지고 씨름을 하고 앉아있었다.

처음 시도는 priority_queue를 이용하는 것이었는데, heap의 크기가 1000을 넘어가면서 heap에 원소를 하나 넣거나 빼는데 너무 많은 시간이 추가로 소요되어 (매 이터레이션 마다 heap에 원소를 넣고 빼므로 계산시간이 10배가 된다.)

결국 시간과의 싸움에서 계속 애먹다가 곰곰히 생각해보니 '짧은 식' 조건이 '사전순으로 가장 앞서는 식' 조건에 우선하므로 BFS로 차근 차근 나가면 굳이 priority_queue를 쓰지않고도 '가장 짧고' '사전순으로 가장 앞서는 식(lexicographically smallest expression)' 을 구하는데 문제가 없다는 것을 알아차릴수 있었다.

상태변수 mem[y][x][val] = '보드상의 (y,x)좌표에 이동하면서 계산식의 결과가 val이 되는 결과식' 으로 정의하면 필요한 상태변수의 대략적인 하한은 w * w * 250 이 된다. 그런데 식을 계산하면서 250이상으로 올라갔다가 내려오는 경우나 1 이하로 내려간 다음에 다시 1이상으로 올라가는 경우가 최적이 될 수도 있기 때문에 val의 범위를 비교적 여유있게 잡아두자. 대략 1000정도로 잡아도 w * w * 1000으로 w가 최대 20이므로 20 * 20 * 1000 = 40,000은 그다지 크지 않다.

초기 상태는 보드상에 숫자로 표기된 각 칸에 처음으로 시작하는 상태가 된다. 각 상태에서 다음 상태로 가는 방법은 16가지가 있다. 상태를 전이하면서 상태변수를 채워가면서 BFS서치를 진행한다. 더 이상 상태변수 mem을 채울 수 없을때 까지 진행한 후 답을 구하면 끗!!

#include <cstdlib> #include <cstdio> #include <string> #include <memory.h> #include <queue> #include <algorithm> using namespace std; char B[21][21]; string mem[2][21][21][1001]; string ans[251]; const int memBase = 500; const int memMax = 1000; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { int w, q; scanf("%d%d", &w, &q); for (int i = 0; i < w; i++) scanf("%s", B[i]); for (int f = 0; f < 2; f++) for (int i = 0; i < w; i++) for (int j = 0; j < w; j++) for (int k = 0; k <= memMax; k++) mem[f][i][j][k] = ""; for (int i = 0; i < 251; i++) ans[i] = ""; queue<pair<int, pair<int, int> > > que[2]; int flag1 = 0; int flag2 = 1; for (int i = 0; i < w; i++) { for (int j = 0; j < w; j++) { if (B[i][j] >= '0' && B[i][j] <= '9') { // first depth mem[flag1][i][j][B[i][j] - '0' + memBase] += B[i][j]; que[flag1].push(make_pair(B[i][j]-'0', make_pair(i, j))); } } } // bfs while (!que[flag1].empty()) { // next depth while (!que[flag1].empty()) { pair<int, pair<int, int> > state = que[flag1].front(); que[flag1].pop(); int val = state.first; int y = state.second.first; int x = state.second.second; // answer if (val >= 1 && val <= 250) { string expr = mem[flag1][y][x][val + memBase]; if (ans[val].size() == 0 || ans[val].size() > expr.size() || ans[val].size() == expr.size() && ans[val] > expr) ans[val] = expr; } // first step to 4-direction for (int d1 = 0; d1 < 4; d1++) { int ny1 = y + dy[d1]; int nx1 = x + dx[d1]; if (ny1 < 0 || ny1 >= w || nx1 < 0 || nx1 >= w) continue; // second step to 4-direction for (int d2 = 0; d2 < 4; d2++) { int ny2 = ny1 + dy[d2]; int nx2 = nx1 + dx[d2]; if (ny2 < 0 || ny2 >= w || nx2 < 0 || nx2 >= w) continue; // next state value int val2 = B[ny2][nx2] - '0'; int nextval = val + val2; if (B[ny1][nx1] == '-') nextval = val - val2; if (nextval + memBase < 0 || nextval + memBase > memMax) continue; // next state expression string expr = mem[flag1][y][x][val + memBase]; expr += B[ny1][nx1]; expr += B[ny2][nx2]; string& nextexpr = mem[flag2][ny2][nx2][nextval + memBase]; // push to next depth if (nextexpr.size() == 0 || expr.size() < nextexpr.size() || expr.size() == nextexpr.size() && expr < nextexpr) { nextexpr = expr; que[flag2].push(make_pair(nextval, make_pair(ny2, nx2))); } } } } // change memory flag1 = 1 - flag1; flag2 = 1 - flag2; } printf("Case #%d:\n", t); for (int i = 0; i < q; i++) { int query; scanf("%d", &query); printf("%s\n", ans[query].c_str()); } } return 0; }


프로그램을 돌려보니 예상보다 실행시간과 메모리 소비가 엄청났다. 인풋 크기가 나름 큰 경우에 효율적인 코드에 조금 더 신경을 써야 할 듯하다. 인풋크기가 큰 문제에 너무 약해 ㅠㅠ