TopCoder SRM 383 Div 2 (완료)

Problem Solving/TopCoder logs 2007. 12. 14. 12:27
SRM 383 .. 새벽 1시 매치이다.. 이번매치에는 한국사람들이 평소보다는 별로 없었다.. 21명이었던가.. 시험기간인가보다.. ;; 250점 문제는 내가 방에서 젤 빨리 풀어서 살짝 놀랐다.. (요즘 계속 놀라고있다..) 나는 내 코딩속도가 빨라지고있다고 자신만만해하고있다가 500점에서 완전 반전 -_-; 안드로를 가고말았다.. 제길.. ㅠ_ㅠ;  코딩속도보다는 두문제정도만 정확하게 풀면 어느정도 rating은 오르는것 같다.. 너무 급하게하려다보니 실수를 하는 경우가 많은데.. 여유를 갖고 침착하게 임해야겠다.. rating은 소폭 상승했다..

방 5등 전체 93등..

사용자 삽입 이미지
이번에도 챌 또 실패.. ㅠ_ㅠ 극악의 챌 성공률.. ㅠ_ㅠ; 250은 젤빨리풀었고 500은 젤늦게 풀었군.. ;

사용자 삽입 이미지
rating은 소폭 상승.. blue에 조금씩 가까워지고있다.. 음.. volatility는 점점 떨어지고.. 힘겨워하고있다.. 1199에 설마 수렴하는건 아니겠지..?



[250] FloorLayout
'-' 모양의 타일과 '|' 모양의 타일이있다.. '-' 는 동서로 같은 모양끼리 연결되고 '|' 는 남북으로 같은 모양끼리 연결된다.. 총 몇개의 component로 되어있는지 구하는 문제..

나는 보자마자 직관적으로 DFS를 이용한 flood-fill 알고리즘을 떠올렸다.. 근데 다른사람 코드를 보니 나와 같은 방법으로 푼사람은 많지 않았다.. 좀 과도한(?) 방법이었는지는 모르겠지만.. 확실한방법으로 바로 코딩에 들어갔더니.. 다른사람보다 빨리 푼것같다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 int n, m;
      9 int check[100][100];
     10 char map[100][100];
     11
     12 void dfs(int u, int v)
     13 {
     14     char ch = map[u][v];
     15     if (ch == '-') {
     16         if (v+1 < m && map[u][v+1] == '-') {
     17             check[u][v+1] = 1;
     18             dfs(u, v+1);
     19         }
     20     }
     21     else if (ch == '|') {
     22         if (u+1 < n && map[u+1][v] == '|') {
     23             check[u+1][v] = 1;
     24             dfs(u+1, v);
     25         }
     26     }
     27     else {
     28         printf("?????\n");
     29     }
     30 }
     31
     32 class FloorLayout {
     33 public:
     34
     35 int countBoards(vector <string> layout)
     36 {
     37     int cnt;
     38     int i, j;
     39     n = layout.size();
     40     m = layout[0].size();
     41     for (i = 0; i < n; i++) {
     42         strcpy(map[i], layout[i].c_str());
     43     }
     44     memset(check, 0, sizeof(check));
     45     cnt = 0;
     46     for (i = 0; i < n; i++) {
     47         for (j = 0; j < m; j++) {
     48             if (check[i][j] == 0) {
     49                 check[i][j] = 1;
     50                 cnt++;
     51                 dfs(i, j);
     52             }
     53         }
     54     }
     55     return cnt;
     56 }
     57
     58 };






[500] Planks
막대기가 주어지고 각각의 막대기를 같은 길이로 잘라서 팔 수 있다.. 막대기 길이 cut하는데 드는 비용과 길이 1미터당 얻는 수익이 주어질때 얻을수 있는 최대 수익을 구하는 문제..

나는 처음 UVa 10003 - Cutting Stick 과 같은 류의 문제라고 생각하고 DP로 어찌어찌 해보려고했는데.. 자세히보니.. 각 길이는 최대 10000 막대기 개수도 최대 50이라서 그냥 길이 1부터 brute force로 다 돌렸다..

흠.. 단순 구현문제인데.. 코딩중 실수를 너무많이해서.. 너무 늦게 풀고말았다.. ㅠ_ㅠ; 500점을 pass한사람중.. 최하위.. ㅠ_ㅠ 답이 제대로 출력되는데.. 제대로 출력이 안된다고 생각하고 쓸데없이 디버깅한게 시간을 많이 잡아먹었다..

이문제의 경우 트릭은 수익이 발생하지않는 경우의 막대기는 그냥 버릴수 있다는것이다.. 흠.. 이걸 모르고 왜 샘플이 안나오나.. 한참 고민했었다.. 이런.. -_-; 왠만한 test case는 샘플에서 다 커버되므로.. 틀릴사람이 별로 없다고생각했는데.. 의외로 많은사람들이 틀렸다.. 흠.. 다들 샘플도 안돌려보고 서밋했나..;

흠.. 급한마음에 그냥 서밋했더니.. 코드가 좀 엉망이다.. min1 이란 변수 이름도 좀 이상하고..;; sum과 temp의 역할도 바껴야정상인데.. -_-

      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
     10 class Planks {
     11 public:
     12
     13 int makeSimilar(vector <int> lengths, int costPerCut, int woodValue)
     14 {
     15     int n;
     16     int i, j, k;
     17     int max1, min1;
     18     int temp, sum;
     19     n = lengths.size();
     20     min1 = lengths[0];
     21     for (i = 1; i < n; i++) {
     22         min1 = max(min1, lengths[i]);
     23     }
     24     max1 = 0;
     25     for (i = 1; i <= min1; i++) {
     26         sum = temp = 0;
     27         for (j = 0; j < n; j++) {
     28             if (lengths[j] < i)
     29                 continue;
     30             sum = 0;
     31             if (lengths[j] % i == 0) {
     32                 k = lengths[j] / i;
     33                 sum += i * (k * woodValue);
     34                 sum -= (k-1) * costPerCut;
     35             }
     36             else {
     37                 k = lengths[j] / i;
     38                 sum += i * k * woodValue;
     39                 sum -= k * costPerCut;
     40             }
     41             if (sum > 0)
     42                 temp += sum;
     43         }
     44         if (temp > max1) {
     45             max1 = temp;
     46         }
     47     }
     48     return max1;
     49 }
     50
     51 };




[1000] HillWalker
2차원의 지도가 나오고 각 cell은 높이를 나타내는 알파벳으로 주어진다.. (A = 0, B = 1, ... , Z = 25, a = 26, b = 27, ..., z = 51) 한번에 위, 아래, 좌, 우, 네 방향으로 이동할 수 있는데 이동하는데 드는 비용은 내려가거나 평지이면 1, 올라가는 경우는 (두 셀의 높이차이)^2 이다.. 또한 높이 차이가 threshold를 넘어가면 이동할 수 없다.. (0, 0)에서 시작해서 timeToDark 시간 이전에 처음위치로 돌아와야할 때 최대 어느 높이까지 올라갈 수 있는지 구하기..

훔.. 매우 귀찮은 문제이다.. 실제 매치에서는 시간이 부족해서 풀지 못했다..


나같은경우 각 cell을 vertex로 생각하고 graph로 구성하여 BFS로 탐색하였다.. 전략은 다음과 같다..

처음위치 -> 임의의 위치 k -> 처음위치

위와 같이 이동하여 시간 내에 도달할 수 있다면 k 위치는 내가 이동할 수 있는 최대 높이의 후보가 된다.. Floyd-Warshall을 이용하여 all pair shortest path를 구하면 간단하지만 vertex의 개수가 최대 625가 되므로 적용 불가능.. -_-; 따라서 BFS로 모든 shortest path를 다 구하면서, k가 이미 도달한 최대높이보나 낮은경우는 cutting했다.. (물론 최악의 경우 이때도 n^3이 된다.. ㅠ_ㅠ list로 구현할 경우 4 * n^2 이군.. list를 애용해야겠다..)

system test를 돌려보니 하나의 case에 대해서 TLE가 나서 graph를 adj-matrix에서 list로 바꾸는 수고를 더했다.. 이제야 드디어 패스..~! 아.. 힘들다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 #include <queue>
      7 using namespace std;
      8 #define INF 99999999
      9
     10 typedef struct _e {
     11     int to, cost;
     12 } EDGE;
     13
     14 int board[100][100];
     15 int h, w;
     16 vector<EDGE> node[1000];
     17
     18 int get_val(char ch)
     19 {
     20     if (ch >= 'A' && ch <= 'Z')
     21         return ch - 'A';
     22     return ch - 'a'+26;
     23 }
     24
     25 int get_idx(int u, int v)
     26 {
     27     if (u < 0 || v < 0 || u >= h || v >= w)
     28         return -1;
     29     return (w*u)+v;
     30 }
     31
     32 class HillWalker {
     33 public:
     34
     35 int highestPoint(vector <string> landscape, int threshold, int timeToDark)
     36 {
     37     int i, j, k;
     38     int temp, size, to;
     39     int a, b, c;
     40     int max1;
     41     int n;
     42     int idx1, idx2;
     43     char buf[100];
     44     int dist[700];
     45     EDGE e;
     46
     47     h = landscape.size();
     48     w = landscape[0].size();
     49     for (i = 0; i < h; i++) {
     50         strcpy(buf, landscape[i].c_str());
     51         for (j = 0; j < w; j++) {
     52             board[i][j] = get_val(buf[j]);
     53         }
     54     }
     55     memset(node, 0, sizeof(node));
     56     for (i = 0; i < h; i++) {
     57         for (j = 0; j < w; j++) {
     58             idx1 = w*i + j;
     59             if (j+1 < w)
     60                 idx2 = w*i + (j+1);
     61             else
     62                 idx2 = -1;
     63             if (idx2 != -1 && (temp = abs(board[i][j] - board[i][j+1])) <= threshold) {
     64                 if (board[i][j] >= board[i][j+1]) {
     65                     e.to = idx2;
     66                     e.cost = 1;
     67                     node[idx1].push_back(e);
     68                 }
     69                 else {
     70                     e.to = idx2;
     71                     e.cost = temp*temp;
     72                     node[idx1].push_back(e);
     73                 }
     74             }
     75
     76             if (j-1 >= 0)
     77                 idx2 = w*i + (j-1);
     78             else
     79                 idx2 = -1;
     80             if (idx2 != -1 && (temp = abs(board[i][j] - board[i][j-1])) <= threshold) {
     81                 if (board[i][j] >= board[i][j-1]) {
     82                     e.to = idx2;
     83                     e.cost = 1;
     84                     node[idx1].push_back(e);
     85                 }
     86                 else {
     87                     e.to = idx2;
     88                     e.cost = temp*temp;
     89                     node[idx1].push_back(e);
     90                 }
     91             }
     92             if (i+1 < h)
     93                 idx2 = w*(i+1) + j;
     94             else
     95                 idx2 = -1;
     96             if (idx2 != -1 && (temp = abs(board[i][j] - board[i+1][j])) <= threshold) {
     97                 if (board[i][j] >= board[i+1][j]) {
     98                     e.to = idx2;
     99                     e.cost = 1;
    100                     node[idx1].push_back(e);
    101                 }
    102                 else {
    103                     e.to = idx2;
    104                     e.cost = temp*temp;
    105                     node[idx1].push_back(e);
    106                 }
    107             }
    108             if (i-1 >= 0)
    109                 idx2 = w*(i-1) + j;
    110             else
    111                 idx2 = -1;
    112             if (idx2 != -1 && (temp = abs(board[i][j] - board[i-1][j])) <= threshold) {
    113                 if (board[i][j] >= board[i-1][j]) {
    114                     e.to = idx2;
    115                     e.cost = 1;
    116                     node[idx1].push_back(e);
    117                 }
    118                 else {
    119                     e.to = idx2;
    120                     e.cost = temp*temp;
    121                     node[idx1].push_back(e);
    122                 }
    123             }
    124         }
    125     }
    126
    127     n = h * w;
    128     dist[0] = 0;
    129     max1 = -1;
    130     for (k = 0; k < n; k++) {
    131         if (max1 > board[k/w][k%w])
    132             continue;
    133         queue<int> q;
    134         for (i = 0; i < n; i++) {
    135             dist[i] = INF;
    136         }
    137         dist[0] = 0;
    138         q.push(0);
    139         while (!q.empty()) {
    140             c = q.front();
    141             q.pop();
    142
    143             size = node[c].size();
    144             for (i = 0; i < size; i++) {
    145                 to = node[c][i].to;
    146                 temp = node[c][i].cost;
    147                 if (dist[to] > dist[c] + temp && dist[c]+temp <= timeToDark) {
    148                     dist[to] = dist[c]+temp;
    149                     q.push(to);
    150                 }
    151             }
    152         }
    153         a = dist[k];
    154
    155         for (i = 0; i < n; i++) {
    156             dist[i] = INF;
    157         }
    158         dist[k] = 0;
    159         q.push(k);
    160         while (!q.empty()) {
    161             c = q.front();
    162             q.pop();
    163             size = node[c].size();
    164             for (i = 0; i < size; i++) {
    165                 to = node[c][i].to;
    166                 temp = node[c][i].cost;
    167                 if (dist[to] > dist[c] + temp && dist[c]+temp+a <= timeToDark) {
    168                     dist[to] = dist[c]+temp;
    169                     q.push(to);
    170                 }
    171             }
    172         }
    173         b = dist[0];
    174         if (a + b <= timeToDark) {
    175             max1 = board[k/w][k%w];
    176         }
    177     }
    178     return max1;
    179 }
    180
    181 };





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

TopCoder SRM 388 Div1  (2) 2008.01.16
TopCoder SRM 387 Div1  (4) 2008.01.10
TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 384 Div2 (완료)  (2) 2007.12.20
TopCoder SRM382 DIV2  (2) 2007.12.13
TopCoder SRM381 DIV2 (완료)  (2) 2007.12.09
TopCoder SRM380 DIV2 (완료)  (0) 2007.12.08
TopCoder SRM 379 Div2 (완료)  (0) 2007.11.29
TopCoder SRM378 DIV2 (완료)  (0) 2007.11.21
  • By helloneo

to Top

티스토리툴바