TopCoder SRM 453.5 (??) Div 1

Problem Solving/TopCoder logs 2009. 11. 26. 22:12
지난번에 스름 453 이 중간에 취소되는 바람에 오늘 새벽에 453.5 가 열렸다..
이번에도 무려 488 등.. rating 은 또 하락했다..
이러다가 올해안에 div2 가는거 아닌지 모르겠네..
rating 한번 화끈하게 올려본게 언제인지 가물가물하다..





Level1 - MazeMaker
2차원 maze 에서 한번에 이동할 수 있는 방향 벡터셋이 주어진다.. 'X' 로 되어있거나 maze 밖으로는 못간다.. '.' 으로 되어있는 곳 중에 가장 도달하는데 오래걸리는 위치 구하기..

전형적인 BFS 문제이다.. start 지점에서 BFS 로 그냥 flooding 시켰음.. ㅎㅎ;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 #define INF 999999999
 11
 12 typedef struct _p {
 13     int x, y;
 14 } POINT;
 15
 16 int check[100][100];
 17
 18 class MazeMaker {
 19 public:
 20
 21 int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)
 22 {
 23     int n;
 24     int x, y;
 25     int row, col;
 26     int max1;
 27     int i, j;
 28     int cur, temp_x, temp_y;
 29     POINT p1, p2;
 30     queue<POINT> q;
 31
 32     row = maze.size();
 33     col = maze[0].size();
 34     for (i = 0; i <row; i++) {
 35         for (j = 0; j < col; j++) {
 36             check[i][j] = INF;
 37         }
 38     }
 39
 40     n = moveRow.size();
 41
 42     p1.x = startRow;
 43     p1.y = startCol;
 44     check[p1.x][p1.y] = 0;
 45     q.push(p1);
 46
 47     while (!q.empty()) {
 48         p1 = q.front();
 49         q.pop();
 50         x = p1.x;
 51         y = p1.y;
 52         cur = check[x][y];
 53
 54         for (i = 0; i < n; i++) {
 55             temp_x = x+moveRow[i];
 56             temp_y = y+moveCol[i];
 57             if (temp_x >= 0 && temp_x < row && temp_y >= 0 && temp_y < col) {
 58                 if (check[temp_x][temp_y] == INF && maze[temp_x][temp_y] == '.') {
 59                     check[temp_x][temp_y] = cur + 1;
 60                     p2.x = temp_x;
 61                     p2.y = temp_y;
 62                     q.push(p2);
 63                 }
 64             }
 65         }
 66     }
 67
 68     max1 = -1;
 69     for (i = 0; i < row; i++) {
 70         for (j = 0; j < col; j++) {
 71             if (maze[i][j] == 'X')
 72                 continue;
 73             max1 = max(max1, check[i][j]);
 74         }
 75     }
 76     if (max1 == INF)
 77         return -1;
 78
 79     return max1;
 80 }
 81
 82 };



Level2 - PlanarGraphShop
어떤 planar graph (V, E) 의 value가 V^3 * E^2 이라고 하자.. 정확히 N 을 만들기 위해서 필요한 planar graph 의 최소 개수 구하기..

graph 이론과 DP 가 짬뽕된 좋은 문제..
이 문제는 planar graph 에서 edge 의 개수를 잘못 세는 바람에 챌 당했다.. 젠장
vertex 의 개수가 v (v >= 3) 일때, planar graph 가 되기 위해선 e <= 3 * v - 6 을 만족해야 한다.. -_-
흠.. 이 사실을 우리방에서 나 빼고 다 알고있었다.. -_-;; 뭥미

뭐 어쨋든.. 이런식으로 나올수 있는 planar graph 의 cost 를 다 구하고..
그 다음부터는 아주 고전적인 DP 문제인 동전교환 문제가 된다..

아.. 이문제땜에 또 잠이 안오는구만..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8 #define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 #define INF 999999999
 11
 12
 13 class PlanarGraphShop {
 14 public:
 15
 16 int bestCount(int N)
 17 {
 18     int i, j, x;
 19     int a, b;
 20     int res;
 21     int dp[50001];
 22     vector<int> item;
 23
 24     item.push_back(1);
 25     item.push_back(8);
 26     item.push_back(8);
 27     item.push_back(9);
 28     for (i = 1; i <= N; i++) {
 29         a = (long long)i*i*i;
 30         if (a > N)
 31             break;
 32         for (j = 0; j <= 3*i-6; j++) {
 33             b = (long long)j*j;
 34             if (a+b > N)
 35                 break;
 36             item.push_back(a+b);
 37         }
 38     }
 39
 40     memset(dp, -1, sizeof(dp));
 41     dp[0] = 0;
 42     for (i = 1; i <= N; i++) {
 43         for (j = 0; j < item.size(); j++) {
 44             x = item[j];
 45             if (i < x)
 46                 continue;
 47             if (dp[i] == -1)
 48                 dp[i] = dp[(int)(i-x)]+1;
 49             else
 50                 dp[i] = min(dp[i], dp[i-x]+1);
 51         }
 52     }
 53     res = dp[N];
 54 printf("res = %d\n", res);
 55     return res;
 56 }
 57
 58 };



Level3 - TheAlmostLuckyNumbers
4 또는 7 로 이루어진 수를 lucky number 라고 한다.. lucky number 로 나누어 떨어지는 수를 almost lucky number 라고 한다.. a 와 b 사이에 almost lucky number 가 몇개 있겠는가?


to be updated..



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

TopCoder SRM 458 Div 1  (0) 2010.01.17
TopCoder SRM 457 Div 1  (0) 2010.01.06
[SRM 456] 2009년 마지막 SRM  (0) 2009.12.23
TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07
[SRM 453] 탑코더 아레나 폭발 -> unrated event  (4) 2009.11.18
TopCoder SRM 450 Div 1  (0) 2009.10.19
TopCoder Member Pilot 2  (0) 2009.10.01
TopCoder SRM 449 Div 1  (0) 2009.09.24
TopCoder SRM 448 Div 1  (0) 2009.09.11
  • By helloneo

to Top

티스토리툴바