음.. 처음해본 상금매치였는데.. 결과가 안좋았다..
두문제 풀고도 둘다 sysfail이라니.. ㅠ_ㅠ 그나마 챌 3개를 성공해서 중간은 유지했다..
세문제 다 쉬웠는데 매우 아쉽다.. 이러다가 계속 DIV2에 머무는거 아닌지. ㅠ_ㅠ
그래도 rating 소폭 상승.. green으로 돌아왔다..

방 8등 전체 307등

사용자 삽입 이미지



[250] CondorcetVoting voting 결과에 대해서 누가 winner인지 구하는 문제.. winner를 한명 뽑을수 없을때 -1을 return한다..

문제를 잘못이해한것인가.. sys fail이다..

흠.. 다른사람 소스를 봐도 여전히 아리송이다..;; 문제해석이 난해한덕분에 챌을 3개나 성공했지만.. 나도 완벽하게 이해못해서 sys fail을 당했다.. 불행중 다행인가 다행중 불행인가..

이제야 제대로 이해..;;
i 후보에게 j 후보보다 좋은 점수를 준 사람이 많으면 i > j 라고 하자..
모든 임의의 j (j != i) 에 대해 i > j 이면 i가 winner이다.. winner가 없을수도있다..

쉬운문제인데.. 문제해석이 어려운문제.. 이런문제 왜 만드는지 모르겠다..

모든 i, j 쌍에 대해서 cnt[i][j] (j보다 i에게 좋은 점수를 준 사람 수)를 기록 한 후.. i 가 모든 다른 j 에 대해서 (i > j) 인지 구했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 class CondorcetVoting {
 10 public:
 11
 12 int winner(vector <string> votes)
 13 {
 14     int size, n;
 15     int i, j, k, res, fl;
 16     int cnt[100][100];
 17     char map[100][100];
 18
 19     size = votes.size();
 20     n = votes[0].size();
 21     for (i = 0; i < size; i++) {
 22         strcpy(map[i], votes[i].c_str());
 23     }
 24     memset(cnt, 0, sizeof(cnt));
 25     for (i = 0; i < n; i++) {
 26         for (j = 0; j < n; j++) {
 27             if (i == j)
 28                 continue;
 29             // i > j 인 사람이 몇명..?
 30             for (k = 0; k < size; k++) {
 31                 if (map[k][i] < map[k][j])
 32                     cnt[i][j]++;
 33             }
 34         }
 35     }
 36     fl = 0;
 37     for (i = 0; i < n; i++) {
 38         for (j = 0; j < n; j++) {
 39             if (i == j)
 40                 continue;
 41             if (cnt[i][j] <= cnt[j][i])
 42                 break;
 43         }
 44         if (j == n) {
 45             fl++;
 46             res = i;
 47         }
 48     }
 49     if (fl == 1)
 50         return res;
 51     return -1;
 52 }
 53
 54 };



[500] SpiralRoute n by m의 직사각형 통로를 spiral형태로 밖에서 시작해서 않으로 이동할때 마지막에 끝나는 위치를 찾는 문제..

다 풀어놓고 critical input하나를 생각을 못했다.. 그러고보니 이런류의 문제는 항상 그부분에서 틀리는거같다..
쉬운문제였는데 아쉽다..


헐.. 문제는 초기화였다.. ㅠ_ㅠ 젠장!! 초기화때문에 틀린게 벌써 몇번째야..!! 초기화는 항상 체크해야겠다..
그냥 simulation을 했다.. 갈수있는데까지 계속 가다가 못가면 stop..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class SpiralRoute {
      9 public:
     10
     11 vector <int> thronePosition(int width, int length)
     12 {
     13     int x1, y1, x2, y2;
     14     int turn, lastx, lasty;
     15     vector<int> res;
     16     x1 = 0;
     17     x2 = width-1;
     18     y1 = 0;
     19     y2 = length-1;
     20     turn = 0;
     21
     22     lastx = lasty = 0;
     23     while (1) {
     24         if (turn == 0) {
     25             lastx = x2;
     26             y1++;
     27         }
     28         else if (turn == 1) {
     29             lasty = y2;
     30             x2--;
     31         }
     32         else if (turn == 2) {
     33             lastx = x1;
     34             y2--;
     35         }
     36         else if (turn == 3) {
     37             lasty = y1;
     38             x1++;
     39         }
     40 printf("x1 = %d, x2 = %d, y1 = %d, y2 = %d\n", x1, x2, y1, y2);
     41         if (x1 > x2 || y1 > y2)
     42             break;
     43         turn++;
     44         turn %= 4;
     45     }
     46     res.push_back(lastx);
     47     res.push_back(lasty);
     48     return res;
     49 }
     50
     51 };




[1000] FloodRelief z가 높은 위치이고 a가 낮은 위치이다.. 물이 고이는곳이 얼마나 있는지 구하는 문제..

시간이 없어서 시도하지 못했다..


그냥 간단히 낮은곳부터 물로 채웠다.. 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 char map[100][100];
     10 char check[100][100];
     11
     12 void dfs(int u, int v, char ch)
     13 {
     14     if (u-1 >= 0 && map[u-1][v] >= ch && check[u-1][v] == 0) {
     15         check[u-1][v] = 1;
     16         dfs(u-1, v, map[u-1][v]);
     17     }
     18     if (v-1 >= 0 && map[u][v-1] >= ch && check[u][v-1] == 0) {
     19         check[u][v-1] = 1;
     20         dfs(u, v-1, map[u][v-1]);
     21     }
     22     if (u+1 < n && map[u+1][v] >= ch && check[u+1][v] == 0) {
     23         check[u+1][v] = 1;
     24         dfs(u+1, v, map[u+1][v]);
     25     }
     26     if (v+1 < m && map[u][v+1] >= ch && check[u][v+1] == 0) {
     27         check[u][v+1] = 1;
     28         dfs(u, v+1, map[u][v+1]);
     29     }
     30 }
     31
     32 class FloodRelief {
     33 public:
     34
     35 int minimumPumps(vector <string> heights)
     36 {
     37     int i, j, k;
     38     int cnt;
     39
     40     n = heights.size();
     41     m = heights[0].size();
     42     for (i = 0; i < n; i++) {
     43         strcpy(map[i], heights[i].c_str());
     44     }
     45
     46     cnt = 0;
     47     memset(check, 0, sizeof(check));
     48     for (i = 'a'; i <= 'z'; i++) {
     49         for (j = 0; j < n; j++) {
     50             for (k = 0; k < m; k++) {
     51                 if (map[j][k] == i && check[j][k] == 0) {
     52                     check[j][k] = 1;
     53                     cnt++;
     54                     dfs(j, k, i);
     55                 }
     56             }
     57         }
     58     }
     59     return cnt;
     60 }
     61
     62 };



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

TopCoder SRM378 DIV2 (완료)  (0) 2007.11.21
TopCoder SRM375 DIV2 (Complete)  (6) 2007.11.11
TopCoder SRM374 DIV2  (3) 2007.11.07
TopCoder SRM 373 Div 2  (0) 2007.10.24
TopCoder SRM 372 Div 2  (8) 2007.10.18
TopCoder SRM 370 Div2  (0) 2007.10.14
TopCoder SRM369 DIV2  (6) 2007.10.05
TopCoder SRM 368 Div 1  (0) 2007.10.03
TopCoder SRM 367 Div 2 (완료)  (10) 2007.09.27
TopCoder SRM 366 DIV 1  (2) 2007.09.18

to Top