TopCoder SRM 425 Div 2 (완료)
어제 새벽 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 를 시도한 사람을 몽땅 챌해버렸다.. ㅋ
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점짜리 코딩하고나니 해결방법이 떠오른 문제..;;
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의 이웃을 다 탐색해야 한다..
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 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 |