어제 새벽 1시에 열린 매치.. -_-;;
미국 day light saving time이 끝나면서 시간이 죄다 1시간 뒤로 밀렸다.. ㅠ_ㅠ
이거.. 아침에 출근해야되는데.. 밤새 머하는건지.. ㅠ_ㅠ;;

이번에는 div2에서 했는데.. 좀 아쉬운감이 있지만.. 나름 성적이 좋았다..
250은 잽싸게 코딩완료하고 서밋했는데.. 아무래도 찜찜해서.. 문제를 다시읽어보니..
내가 문제를 잘못 이해하고있었다.. 덕분에 또 리서밋..;; 요즘 매번 리서밋때문에 고전한다.. ㅠ_ㅠ
500은 좀 읽다가 어려운거같아서 포기하고 1000을 열었는데..
솔루션이 잘 안떠오르는 500과 코딩이 좀 짜증나는 1000중에 뭘 풀까 하다가.. 그냥 1000을 노렸다..
나중에 1000도 서밋하고 시간이 좀 남길래 500도 대충 풀어서 서밋했는데..
심혈을 기울인 1000은 fail하고 대충 푼 500이 pass해버렸다.. 이거 멍미..;;

250을 처음에 나처럼 문제를 잘못이해한 사람이 많아서 챌로만 무려 225점을 얻었다..
덕분에 낮은 코딩점수에도 불구하고 괜찮은 성적을 올렸다..

흠.. 1000점짜리는 backtracking으로 풀었는데.. 왜 WA가 났을까.. ?.?

사용자 삽입 이미지



Level1 - InverseFactoring

input으로 어떤수 N의 proper factor가 들어온다.. proper factor란 1과 N을 제외한 N의 약수이다.. 이 factor들을 이용하여 N을 구하기..

나는 주어진 factor의 모든 lcm을 구한다음 그게 factor중 가장 큰 수와 같다면 가장 작은 factor를 한번 더 곱해서 구했다.. input이 1가 N을 제외한 factor이므로.. 나중에 다른 사람 코드를 보니.. 간단히 factors 중에서 가장 작은수와 가장 큰수를 곱하면 되는거였다.. 음.. 왜그렇지.. -_-

많은 사람들이 문제를 잘못 이해해서 마구 fail 했다.. 예를들어 input이 {3} 인 경우 답은 9가 되어야하는데 6으로 출력한 사람이 많았다.. 6이 답이 되려면 input은 {2, 3} 이 되어야하는데..;; 덕분에 코드중에 *2 를 시도한 사람을 몽땅 챌해버렸다.. ㅋ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int gcd(int a, int b)
  9 {
 10     if (b == 0)
 11         return a;
 12     return gcd(b, a % b);
 13 }
 14
 15 int lcm(int a, int b)
 16 {
 17     return (int)((long long)a * b / gcd(a, b));
 18 }
 19
 20 class InverseFactoring {
 21 public:
 22
 23 int getTheNumber(vector <int> factors)
 24 {
 25     int size;
 26     int i;
 27     int res;
 28     int max1, min1;
 29     size = factors.size();
 30     res = 1;
 31     max1 = 1;
 32     min1 = 2000000000;
 33     for (i = 0; i < size; i++) {
 34         if (factors[i] > max1)
 35             max1 = factors[i];
 36         if (factors[i] < min1)
 37             min1 = factors[i];
 38         res = lcm(res, factors[i]);
 39     }
 40     if (max1 == res)
 41         return res * min1;
 42     return res;
 43 }
 44
 45 };




Level2 - CrazyBot

어떤 로봇이 동, 서, 남, 북으로 각각 이동할 확률이 percentage로 주어진다.. N칸을 이동할 경우 로봇이 지났던 지점을 다시 지나지 않고 N칸을 다 이동할 확률 구하기..

backtracking으로 풀었다.. -_-;; 우선 중앙에서 시작해서 한번 갔던곳을 다시 지나지 않도록 해서 모든 방향으로 다 이동해보았다.. 그리고 N step 이동했을때 그동안의 path를 이용해서 확률을 구했다.. -_- N이 14라서 좀 망설이긴 했지만.. 한번 지난 곳은 다시 안지나므로.. 답은 14! 보다 훨씬 작을거라고 믿고.. 그냥 몽땅 다구했다.. ㅋㅋ 1000점 문제도 backtracking으로 접근했는데.. 오늘 backtracking 날인가..;;

사실 이문제는 처음에 잘 생각을 못했는데.. 1000점짜리 코딩하고나니 해결방법이 떠오른 문제..;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 char check[100][100];
  9 int path[100];
 10 double p[5];
 11 double sum;
 12 int n;
 13
 14 void dfs(int u, int v, int cnt, int di)
 15 {
 16     int i;
 17     double temp;
 18     path[cnt] = di;
 19     if (cnt == n) {
 20         temp = 1.0;
 21         for (i = 1; i <= cnt; i++) {
 22             temp *= p[path[i]];
 23         }
 24         sum += temp;
 25         return ;
 26     }
 27     if (check[u+1][v] == 0) {
 28         check[u+1][v] = 1;
 29         dfs(u+1, v, cnt+1, 1);
 30         check[u+1][v] = 0;
 31     }
 32     if (check[u][v+1] == 0) {
 33         check[u][v+1] = 1;
 34         dfs(u, v+1, cnt+1, 2);
 35         check[u][v+1] = 0;
 36     }
 37     if (check[u-1][v] == 0) {
 38         check[u-1][v] = 1;
 39         dfs(u-1, v, cnt+1, 3);
 40         check[u-1][v] = 0;
 41     }
 42     if (check[u][v-1] == 0) {
 43         check[u][v-1] = 1;
 44         dfs(u, v-1, cnt+1, 4);
 45         check[u][v-1] = 0;
 46     }
 47 }
 48
 49 class CrazyBot {
 50 public:
 51
 52 double getProbability(int N, int east, int west, int south, int north)
 53 {
 54     p[1] = (double)east / 100.0;
 55     p[2] = (double)north / 100.0;
 56     p[3] = (double)west/ 100.0;
 57     p[4] = (double)south/ 100.0;
 58     n = N;
 59
 60     sum = 0;
 61     memset(check, 0, sizeof(check));
 62     check[50][50] = 1;
 63     check[51][50] = 1;
 64     dfs(51, 50, 1, 1);
 65     check[51][50] = 0;
 66
 67     check[50][51] = 1;
 68     dfs(50, 51, 1, 2);
 69     check[50][51] = 0;
 70
 71     check[49][50] = 1;
 72     dfs(49, 50, 1, 3);
 73     check[49][50] = 0;
 74
 75     check[50][49] = 1;
 76     dfs(50, 49, 1, 4);
 77     check[50][49] = 0;
 78 printf("sum = %lf\n", sum);
 79     return sum;
 80 }
 81
 82 };




Level3 - PiecesMover

5 by 5 board에 N개의 * 이 있다.. 이 * 들을 이동시켜서 모두 connected 된 상태로 만들고 싶다.. connected는 서로 위 아래 양옆 중 하나의 방향으로 이웃한 경우.. *들의 최소 이동 거리 구하기

우선 backtracking으로 모든 가능한 connected component를 다 구하고.. 현재 놓여있는 점들을 구한 CC에 매칭을 시킨다.. 어떤 매칭이 최적인지 모르므로 이 경우에도 모든 경우를 다 해본다.. 2중 backtracking이 될수도 있겠지만.. -_-; next_permutation이란 편리한 함수가 있으므로 이를 이용하면 쉽다..

실제 매치때 WA받은 이유는.. 다음 상태공간을 탐색할 때, 가장 마지막에 넘어왔던 위치에서의 이웃한 4방향만 구했기 때문이다.. 지금까지 놓여진 모든 piece의 이웃을 다 탐색해야 한다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 typedef struct _p {
  9     int x, y;
 10 } POINT;
 11
 12 POINT pt[5], pt2[5];
 13 int r[10][10];
 14 int min1, sum;
 15 int n;
 16
 17 void dfs(int u, int v, int cnt)
 18 {
 19     int idx[5];
 20     int i, j, k;
 21
 22     if (cnt == n) {
 23         for (i = 0; i < n; i++) {
 24             idx[i] = i;
 25         }
 26         k = 0;
 27         for (i = 0; i < 5; i++) {
 28         for (j = 0; j < 5; j++) {
 29             if (r[i][j] == 1) {
 30                 pt2[k].x = i;
 31                 pt2[k].y = j;
 32                 k++;
 33             }
 34         }
 35         }
 36         do {
 37             sum = 0;
 38             for (i = 0; i < n; i++) {
 39                 sum += abs(pt[idx[i]].x-pt2[i].x) + abs(pt[idx[i]].y-pt2[i].y);
 40             }
 41             if (sum < min1)
 42                 min1 = sum;
 43         } while (next_permutation(idx, idx+n));
 44         return ;
 45     }
 46     for (u = 0; u < 5; u++) {
 47     for (v = 0; v < 5; v++) {
 48     if (r[u][v]) {
 49     if (u+1 < 5 && r[u+1][v] == 0) {
 50         r[u+1][v] = 1;
 51         dfs(u+1, v, cnt+1);
 52         r[u+1][v] = 0;
 53     }
 54     if (v+1 < 5 && r[u][v+1] == 0) {
 55         r[u][v+1] = 1;
 56         dfs(u, v+1, cnt+1);
 57         r[u][v+1] = 0;
 58     }
 59     if (v-1 >= 0 && r[u][v-1] == 0) {
 60         r[u][v-1] = 1;
 61         dfs(u, v-1, cnt+1);
 62         r[u][v-1] = 0;
 63     }
 64     if (u-1 >= 0 && r[u-1][v] == 0) {
 65         r[u-1][v] = 1;
 66         dfs(u-1, v, cnt+1);
 67         r[u-1][v] = 0;
 68     }
 69     }
 70     }
 71     }
 72 }
 73
 74 class PiecesMover {
 75 public:
 76
 77 int getMinimumMoves(vector <string> board)
 78 {
 79     char map[10][10];
 80     int i, j, k;
 81     for (i = 0; i < 5; i++) {
 82         strcpy(map[i], board[i].c_str());
 83     }
 84     k = 0;
 85     for (i = 0; i < 5; i++) {
 86         for (j = 0; j < 5; j++) {
 87             if (map[i][j] == '*') {
 88                 pt[k].x = i;
 89                 pt[k].y = j;
 90                 k++;
 91             }
 92         }
 93     }
 94     n = k;
 95     memset(r, 0, sizeof(r));
 96     min1 = 2000000000;
 97     for (i = 0; i < 5; i++) {
 98         for (j = 0; j < 5; j++) {
 99             if (r[i][j] == 0) {
100                 r[i][j] = 1;
101                 dfs(i, j, 1);
102                 r[i][j] = 0;
103             }
104         }
105     }
106 printf("ret = %d\n", min1);
107     return min1;
108 }
109
110 };


 

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

TCO09 Qual 1  (0) 2009.02.25
TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07
TopCoder SRM 428 Div 1  (0) 2008.12.03
탑코더 스름 426 디비젼 1  (0) 2008.11.25
TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13
TopCoder SRM 422 Div 1  (4) 2008.10.19
TopCoder SRM 421 Div 1  (0) 2008.10.12
TopCoder SRM 420 Div 2  (0) 2008.10.03
TopCoder SRM 418 Div 2  (0) 2008.09.21
TopCoder SRM 417 Div 2  (0) 2008.09.13

Leave a Comment


to Top