TopCoder Member Pilot 2

Problem Solving/TopCoder logs 2009. 10. 1. 20:51
22일 밤 12시에 열린 매치..~
이번 매치는 정식 SRM 이 아니고 member pilot 매치로 지난번에 첫번째 매치가 열렸었다..
이번에도 역시 not rated event 였다..

300점짜리는 문제를 읽다보니 어려워보이고 코딩도 까다로울꺼같아서 그냥 패스..~ unrated 이니까!
근데 나중에 다시 읽어보니 쉬운문제였다.. -_-;;
450 점은 MST와 DP가 짬뽕된 상당히 괜찮은 문제이다..
이문제는 여러번 삽질끝에 거의 다 풀었는데.. 뭔가 조건 하나를 빠뜨린게 있어서..
샘플 하나가 안나와서 결국 서밋을 못했다..
평소같았으면 매우 아쉬웠겠지만.. 뭐.. unrated 인데 이정도 쯤이야..




Level1 - TwistedMatrix
matrix A 를 한번의 operation 으로 B 로 만드는 문제.. '?' 에는 0 또는 1 아무거나 들어갈 수 있다.. 이때 가능한 lexy-smallest B 구하기.. 여기서 operation 이란 2 by 2 짜리 sub matrix 를 90도 좌로 또는 우로 회전하는것을 말한다..

단순히 모든 가능한 2 by 2 sub matrix를 회전해서 비교했다..
쉬운문제인데 나름 조건이 까다로운게 있어서.. 코드가 복잡해졌다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10
 11 int n, m;
 12
 13 int is_match(char a[][50], char b[][50], char c[][50])
 14 {
 15     int i, j;
 16     for (i = 0; i < n; i++) {
 17         for (j = 0; j < m; j++) {
 18             if (a[i][j] == '?' && b[i][j] == '?') {
 19                 c[i][j] = '0';
 20                 continue;
 21             }
 22             else if (b[i][j] == '?') {
 23                 c[i][j] = a[i][j];
 24                 continue;
 25             }
 26             else if (a[i][j] == '?') {
 27                 c[i][j] = b[i][j];
 28                 continue;
 29             }
 30             if (a[i][j] != b[i][j])
 31                 return 0;
 32             c[i][j] = b[i][j];
 33         }
 34     }
 35     return 1;
 36 }
 37
 38 class TwistedMatrix {
 39 public:
 40
 41 vector <string> solve(vector <string> A, vector <string> B)
 42 {
 43     int i, j, k;
 44     char map1[50][50], map2[50][50], temp[50][50];
 45     char temp2[50][50];
 46     vector<string> res;
 47     n = A.size();
 48     m = A[0].size();
 49     for (i = 0; i < n; i++) {
 50         strcpy(map1[i], A[i].c_str());
 51         strcpy(map2[i], B[i].c_str());
 52     }
 53     memset(temp2, 0, sizeof(temp2));
 54     for (i = 0; i < n-1; i++) {
 55         for (j = 0; j < m-1; j++) {
 56             for (k = 0; k < n; k++) {
 57                 strcpy(temp[k], map1[k]);
 58             }
 59             temp[i][j] = map1[i+1][j];
 60             temp[i][j+1] = map1[i][j];
 61             temp[i+1][j] = map1[i+1][j+1];
 62             temp[i+1][j+1] = map1[i][j+1];
 63             if (is_match(temp, map2, temp2)) {
 64 /*
 65 printf("--- matched (%d, %d)\n", i, j);
 66 for (k = 0; k < n; k++) {
 67 printf("%s\n", temp2[k]);
 68 }
 69 printf("\n");
 70 */
 71                 if (res.size() == 0) {
 72                     for (k = 0; k < n; k++) {
 73                         res.push_back(temp2[k]);
 74                     }
 75                 }
 76                 else {
 77                     string s;
 78                     int fl = 1;
 79                     for (k = 0; k < n; k++) {
 80                         s = temp2[k];
 81                         if (s > res[k]) {
 82                             fl = 0;
 83                             break;
 84                         }
 85                         else if (s < res[k]) {
 86                             break;
 87                         }
 88                     }
 89                     if (fl) {
 90                         res.clear();
 91                         for (k = 0; k < n; k++) {
 92                             res.push_back(temp2[k]);
 93                         }
 94                     }
 95                 }
 96             }
 97             temp[i][j] = map1[i][j+1];
 98             temp[i][j+1] = map1[i+1][j+1];
 99             temp[i+1][j] = map1[i][j];
100             temp[i+1][j+1] = map1[i+1][j];
101             if (is_match(temp, map2, temp2)) {
102 /*
103 printf("--- matched (%d, %d)\n", i, j);
104 for (k = 0; k < n; k++) {
105 printf("%s\n", temp2[k]);
106 }
107 printf("\n");
108 */
109                 if (res.size() == 0) {
110                     for (k = 0; k < n; k++) {
111                         res.push_back(temp2[k]);
112                     }
113                 }
114                 else {
115                     string s;
116                     int fl = 1;
117                     for (k = 0; k < n; k++) {
118                         s = temp2[k];
119                         if (s > res[k]) {
120                             fl = 0;
121                             break;
122                         }
123                         else if (s < res[k]) {
124                             break;
125                         }
126                     }
127                     if (fl) {
128                         res.clear();
129                         for (k = 0; k < n; k++) {
130                             res.push_back(temp2[k]);
131                         }
132                     }
133                 }
134             }
135         }
136     }
137     return res;
138 }
139
140 };



Level2 - TransportationNetwork
n개의 city가 있고 임의의 city 끼리 모두 통행이 가능하도록 길 또는 airport를 만들려고할때 이때의 최소비용 구하기.. city u -> v 로 가려면 u v 사이에 길이 있거나 둘다 airport 가 있으면 된다.. airport 를 짓는데 드는 비용과 길을 만드는데 드는 비용은 각각 input으로 들어온다

MST (Mimimum Spanning Tree)와 DP가 짬뽕된 매우 좋은 문제..
Prims 알고리즘을 기반으로 MST 를 만들어나가는데..

sum[i][0] = i 번째 vertex까지 선택하고 아직 airport 가 하나도 없는 경우 최소값
sum[i][1] = i 번째 vertex까지 선택하고 airport 를 한개 이상 지은 경우 최소값

로 정의하고 최소비용을 만드는 vertex를 하나씩 선택해나가면 된다..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 #include <queue>
  8 using namespace std;
  9 #define min(x, y) ((x) > (y) ? (y) : (x))
 10 //#define max(x, y) ((x) > (y) ? (x) : (y))
 11 #define INF 999999999999.0
 12 #define MAXN 200
 13 #define EPS 1e-12
 14
 15 int n;
 16 double w[200][200];
 17 double A, R;
 18
 19 double get_dist(double x1, double y1, double x2, double y2)
 20 {
 21     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 22 }
 23
 24 double prim()
 25 {
 26     int i, j;
 27     int vnear, cnt;
 28     int nearest[MAXN];
 29     double min1;
 30     double sum[200][2];
 31     double distance[MAXN];
 32
 33     cnt = 0;
 34     sum[0][0] = 0;
 35     sum[0][1] = A;
 36     for (i = 1; i < n; i++) {
 37         nearest[i] = 0;
 38         distance[i] = w[0][i];
 39     }
 40     for (j = 1; j < n; j++) {
 41         min1 = INF;
 42         for (i = 1; i < n; i++) {
 43             if (distance[i] > 0 && distance[i] < min1) {
 44                 min1 = distance[i];
 45                 vnear = i;
 46             }
 47         }
 48         sum[j][0] = sum[j-1][0] + w[nearest[vnear]][vnear];
 49         sum[j][1] = sum[j-1][0] + 2 * A;
 50         sum[j][1] = min(sum[j][1], sum[j-1][1] + A);
 51         sum[j][1] = min(sum[j][1], sum[j-1][1] + w[nearest[vnear]][vnear]);
 52 //printf("sum[%d][0] = %lf, sum[%d][1] = %lf\n", j, sum[j][0], j, sum[j][1]);
 53
 54         distance[vnear] = -1;
 55         for (i = 1; i < n; i++) {
 56             if (w[i][vnear] < distance[i]) {
 57                 distance[i] = w[i][vnear];
 58                 nearest[i] = vnear;
 59             }
 60         }
 61     }
 62     return min(sum[n-1][0], sum[n-1][1]);
 63 }
 64
 65
 66 class TransportationNetwork {
 67 public:
 68
 69 double minCost(vector <int> X, vector <int> Y, double r, double a)
 70 {
 71     int i, j;
 72     n = X.size();
 73     if (n == 1)
 74         return 0.0;
 75     if (fabs(r) < EPS || fabs(a) < EPS)
 76         return 0.0;
 77     for (i = 0; i < n; i++) {
 78         for (j = 0; j < n; j++) {
 79             w[i][j] = get_dist(X[i], Y[i], X[j], Y[j]) * r;
 80         }
 81         w[i][i] = INF;
 82     }
 83     A = a;
 84     R = r;
 85     return prim();
 86 }
 87
 88 };



Level3 - PrefixFreeCode



to be updated..


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

TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07
TopCoder SRM 453.5 (??) Div 1  (0) 2009.11.26
[SRM 453] 탑코더 아레나 폭발 -> unrated event  (4) 2009.11.18
TopCoder SRM 450 Div 1  (0) 2009.10.19
TopCoder SRM 449 Div 1  (0) 2009.09.24
TopCoder SRM 448 Div 1  (0) 2009.09.11
Beta SRM (Member-Run Round)  (0) 2009.08.19
[SRM 446] 매치가 뭐 이래..?! (Unchallengeable Match)  (6) 2009.08.09
TopCoder SRM 445 Div 1  (0) 2009.07.24
  • By helloneo

to Top

티스토리툴바