새벽 1시에 있었던 상금매치.. 상금매치라서 그런지 엄청나게 많은 사람이 몰렸다.. 대략 20분 정도를 남기고 1500명이 다 찼던 것 같다.. 근데 1시에 예정되어있던 매치는 시스템에 문제가 생겨서.. 20분 지연되었더.. 무슨 listener가 동작을 안한다나 뭐래나.. 그동안 채팅방에서는 도대체 listening 하는사람이 누구냐는 황당한(?) 질문들도 올라오고.. 뭐 조금 특이한 매치였다..

이번 매치는 다른 상금매치와는 다르게 약간 쉬웠던것 같다.. 나는 아쉽게도 두문제밖에 못풀었지만..;; 250점 문제는 매우 쉬운문제임에도 불구하고 삽질하다가 순위 쭈욱 밀리고.. 그대신 500에서 남들보다 좀 빨리 풀어서 2등까지 올라갔다.. 코딩단계에서는 5등까지 밀려났지만.. 챌에서 다들 줄줄이 떨어지면서 2등을 유지했다.. 덕분에 다시 1군 복귀.. 이제부터 열심히 해야지!!

방 2등 전체 56등..

사용자 삽입 이미지



[250] BreakingTheCode
input으로 code와 message가 들어온다.. code의 첫번째 문자는 "01", 두번째 문자는 "02", ..., 26번째 문자는 "26"으로 encoding 된다.. message가 encoding 된 문자열이면 decoding하고, decoding된 문자열이면 encoding 해서 return

문제 파악을 잘못해서 말리고.. 코딩에서 말리고.. 안드로메다로 여러번 왔다갔다했던 문제.. ㅠ_ㅠ input으로 encoding할 문자열만 들어오는줄 알았는데 encoding 된 문자열도 들어오는 것이었다.. 왜 샘플이 안나오나 한참 고민하다 시간을 다 까먹었다.. 음.. 그래도 500점만 잘 풀면 승산이 있다는 생각에 느긋하게 풀었다.. 153점에 submit!!!

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cctype>
  7 using namespace std;
  8
  9 class BreakingTheCode {
 10 public:
 11
 12 string decodingEncoding(string code, string message)
 13 {
 14     int i, j, k;
 15     char c[128], m[128];
 16     char buf[128];
 17     string res;
 18     strcpy(c, code.c_str());
 19     strcpy(m, message.c_str());
 20     k = 0;
 21     if (isdigit(m[0])) {
 22         for (i = 0; i < strlen(m); i+=2) {
 23             j = m[i] - '0';
 24             j *= 10;
 25             j += m[i+1] - '0';
 26             buf[k++] = c[j-1];
 27         }
 28         buf[k] = 0;
 29         res = buf;
 30     }
 31     else {
 32         for (i = 0; i < strlen(m); i++) {
 33             for (j = 0; j < strlen(c); j++) {
 34                 if (m[i] == c[j])
 35                     break;
 36             }
 37             buf[k++] = ((j+1) / 10) + '0';
 38             buf[k++] = ((j+1) % 10) + '0';
 39         }
 40         buf[k] = 0;
 41         res = buf;
 42     }
 43     return res;
 44 }
 45
 46 };




[500] SortingGame
input으로 숫자 배열과 k가 주어지고.. 이 배열을 sort하려고 한다. 배열에서 k개의 연속된 sub-array를 뒤집는 것이 유일한 연산 방법일때, sort하기 위해서 필요한 최소 연산 횟수를 구하기..

이 문제는 문제를 읽자마자 솔루션이 바로 떠올랐다.. 11198 - Dancing Digits 문제와 비슷하다.. 물론 Dancing Digits 문제가 훨씬 더 복잡하다.. ㅋ

BFS로 모든 경우를 다 탐색했다.. 다른 사람 코드를 보니 같은 방법임에도 불구하고 코드가 훨씬 더 간결했다.. 흠.. STL 사용이 익숙치 않아서 코드가 많이 길어졌다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 #include <map>
  8 using namespace std;
  9
 10 int n;
 11
 12 int make_int(int* board)
 13 {
 14     int i;
 15     int r = 0;
 16     for (i = 0; i < n; i++) {
 17         r *= 10;
 18         r += board[i];
 19     }
 20     return r;
 21 }
 22
 23 class SortingGame {
 24 public:
 25
 26 int fewestMoves(vector <int> board, int k)
 27 {
 28     int a;
 29     int i, j, l, x, right, left, temp;
 30     int b[50], c[50];
 31     map<int, int> check;
 32     queue<int> q;
 33     n = board.size();
 34     for (i = 0; i < n; i++) {
 35         b[i] = board[i];
 36     }
 37     a = make_int(b);
 38     q.push(a);
 39     check[a] = 0;
 40
 41     while (!q.empty()) {
 42         a = q.front();
 43         temp = a;
 44         q.pop();
 45         for (i = n-1; i >= 0; i--) {
 46             b[i] = temp % 10;
 47             temp /= 10;
 48         }
 49         for (i = 1; i < n; i++) {
 50             if (b[i] < b[i-1])
 51                 break;
 52         }
 53         if (i == n) {
 54 printf("return %d..\n", check[a]);
 55             return check[a];
 56         }
 57         for (i = 0; i+k-1 < n; i++) {
 58             for (j = 0; j < n; j++) {
 59                 c[j] = b[j];
 60             }
 61             left = i;
 62             right = i+k-1;
 63             for (j = left, l = right; j <= right; j++, l--) {
 64                 c[j] = b[l];
 65             }
 66             x = make_int(c);
 67             if (check.find(x) == check.end()) {
 68                 check[x] = check[a] + 1;
 69                 q.push(x);
 70             }
 71         }
 72     }
 73 printf("return -1..\n");
 74     return -1;
 75 }
 76
 77 };




[1000] CollectingMarbles
구슬의 무게가 주어지고, 가방의 크기와 가방의 개수가 주어진다.. (모든 가방은 같다) 이때, 최대 몇개의 구슬을 가져갈 수 있는지 구하는문제.. 즉, 0/1 Knapsack에서 가방이 여러개라고 생각하면 된다.

이 문제는 전형적인 recursion + memorization 문제.. 흠.. 항상 이런 류의 문제를 놓친다.. 흠..

현재 가방에 지금까지 담지않은 모든 구슬을 한개씩 넣어보고 또는 넣지않고 다음가방으로 넘어가는 방법으로 진행한다.. 그 중 최대값을 return한다.. 중복된 상태를 계산하지않기 위해 memorization 기법을 활용한다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 int memo[1<<13][21][11];
 10 int w[20];
 11 int c, n;
 12
 13 int recur(int mask, int u, int v)
 14 {
 15     int i, max1;
 16     if (memo[mask][u][v] != -1)
 17         return memo[mask][u][v];
 18     if (v == 0)
 19         return 0;
 20     max1 = 0;
 21     for (i = 0; i < n; i++) {
 22         if (mask & (1 << i))
 23             continue;
 24         if (w[i] > u)
 25             continue;
 26         max1 = max(max1, recur(mask | (1 << i), u - w[i], v) + 1);
 27     }
 28     max1 = max(max1, recur(mask, c, v-1));
 29     return memo[mask][u][v] = max1;
 30 }
 31
 32 class CollectingMarbles {
 33 public:
 34
 35 int mostMarbles(vector <int> marblesWeights, int bagCapacity, int numberOfBags)
 36 {
 37     int i;
 38     n = marblesWeights.size();
 39     for (i = 0; i < n; i++) {
 40         w[i] = marblesWeights[i];
 41     }
 42     c = bagCapacity;
 43     memset(memo, -1, sizeof(memo));
 44     return recur(0, c, numberOfBags);
 45 }
 46
 47 };


'Problem Solving > TopCoder logs' 카테고리의 다른 글

TopCoder SRM 401 Div1  (2) 2008.05.07
TopCoder SRM 400 Div 1  (0) 2008.05.02
리눅스에서 탑코더하기..  (0) 2008.05.01
TopCoder SRM 399 Div 1  (0) 2008.04.25
TopCoder SRM 398 Div1  (0) 2008.04.16
TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
SRM 395 Div1  (0) 2008.04.09
TopCoder SRM 394 Div 1  (2) 2008.03.24
흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27

Leave a Comment


to Top