탑코더 후기 올리는것도 은근히 귀찮다.. 더군다나 최근에 몇차례 연빵으로 있어서.. 아직 밀린 문제들이 많은데.. 흠.. ;; 부지런히 해야겠다.. 더군다나 나의 블로그의 글들이 거의 탑코더 후기로 채워지고 있다.. 흠.. 이러면 안되는데.. 포스팅도 자주자주 해야겠다..

SRM 382는 수요일 아침 11시에 있었던 매치..;; 역시.. 아침 11시는 정말 컨디션 최악이라는것을 다시한번 느꼈다.. 왜 아침만되면 코딩이안되는지.. -_- 단순코딩문제를 계속 헤매다가 정말 간신히 풀었다.. 훔

1) 매번 할때마다 단순 코딩문제만 풀고.. 정작 풀고싶은 DP라든지 알고리즘 쓰는 문제는 죄다 놓치는것 같다.. 흠.. 이러면 안되는데..;; ㅠ_ㅠ

2) 최근에 한국 유저가 많이 등록함에따라서.. (왠만한 매치에는 거의 항상 30명이 넘는다..) 종종 같은 방에서 만난다.. 좋은 현상인것같다.. 다같이 선전해서 한국이 위대하다는것을 보여줬으면 좋겠다..

3) 우리나라가 네덜란드를 제치고 세계 10위 마크~!!! 내가 탑코더에 열심히 참여한 덕분에 10위 탈환이 좀 늦어지지않았나 생각해본다 (응? 응?)

방 10등 전체 228등..


사용자 삽입 이미지


사용자 삽입 이미지



[250] ContiguousSubsequences

more..

숫자 배열이 들어오고.. 길이가 K이상인 연속된 subsequence중에서 평균이 가장 큰 sequence의 앞과 맨 끝 index를 구하기.. 답이 여러개일 경우 가장 긴 sequence 그중에서도 index가 젤 빠른걸 골라야한다.. 그걸 모르고 왜 sample이 안나오는지 한참 고민했다..

음.. 단순 구현문제인데 코딩에서 말리는바람에 한참 늦게풀었다.. 나같은경우 처음 시작부터 cumulative sum을 구해놓고 n^2으로 구했다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class ContiguousSubsequences {
      9 public:
     10
     11 vector <int> findMaxAverage(vector <int> a, int K)
     12 {
     13     int n, sum;
     14     int i, j;
     15     int x, y;
     16     double max1, avg;
     17     int arr[100];
     18     vector<int> res;
     19     n = a.size();
     20     max1 = -1.0;
     21     memset(arr, 0, sizeof(arr));
     22     arr[0] = a[0];
     23     for (i = 1; i < n; i++) {
     24         arr[i] += arr[i-1] + a[i];
     25     }
     26     for (i = n; i >= K; i--) {
     27         for (j = 0; j+i-1 < n; j++) {
     28             if (j == 0)
     29                 sum = arr[j+i-1];
     30             else
     31                 sum = arr[j+i-1] - arr[j-1];
     32             avg = (double)sum / (double)i;
     33             if (avg > max1) {
     34                 max1 = avg;
     35                 x = j;
     36                 y = j+i-1;
     37             }
     38         }
     39     }
     40     res.push_back(x);
     41     res.push_back(y);
     42 printf("x, = %d, y = %d\n", x, y);
     43     return res;
     44 }
     45
     46
     47 };





[500] CollectingRiders

more..

k-rider는 체스판에서 knight와 같이 움직이는데 한번에 k번 이하의 knight move를 움직일 수 있다.. 체스판에있는 모든 k-rider를 한곳으로 모으는데드는 최소비용 구하기..

솔루션은 에디토리얼을 참고했다.. 우선 모든 rider는 1-rider라고 생각하고 모든 지점에대한 all-pair shortest path를 구한다.. 그리고 k-rider에 대해서 적용하면 A 지점에서 B 지점으로 이동시 드는 비용은 ceil(dist(A, B) / k)이 된다.. (dist(A,B) = 1-rider가 A에서 B로 이동시 드는 비용)

all-pair shortest path는 모든 쌍에 대해서 bfs로 다 돌렸다.. 그리고나서 모든 지점에 대해서 모든 rider를 위치했을때 드는 비용을 다 구해보고 그중 최소값을 취한다..

아.. 코딩하는데 드럽게 오래걸렸다.. 이런문제 나오면 도대체 어케풀어.. ㅠ_ㅠ;;;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 using namespace std;
  8
  9 typedef struct _p {
 10     int x, y;
 11 } POINT;
 12
 13 int n, m;
 14 int map[11][11][11][11];
 15 char b[100][100];
 16
 17 int bfs(POINT s, POINT t)
 18 {
 19     int check[11][11];
 20     int x, y, cnt;
 21     POINT p1, p2;
 22
 23     memset(check, -1, sizeof(check));
 24
 25     queue<POINT> q;
 26     q.push(s);
 27     check[s.x][s.y] = 0;
 28
 29     while (!q.empty() && check[t.x][t.y] == -1) {
 30         p1 = q.front();
 31         q.pop();
 32         cnt = check[p1.x][p1.y];
 33         x = p1.x;
 34         y = p1.y;
 35
 36         if (x+1 < n && y+2 < m && check[x+1][y+2] == -1) {
 37             check[x+1][y+2] = cnt+1;
 38             p2.x = x+1;
 39             p2.y = y+2;
 40             q.push(p2);
 41         }
 42         if (x+2 < n && y+1 < m && check[x+2][y+1] == -1) {
 43             check[x+2][y+1] = cnt+1;
 44             p2.x = x+2;
 45             p2.y = y+1;
 46             q.push(p2);
 47         }
 48         if (x-1 >= 0 && y+2 < m && check[x-1][y+2] == -1) {
 49             check[x-1][y+2] = cnt+1;
 50             p2.x = x-1;
 51             p2.y = y+2;
 52             q.push(p2);
 53         }
 54         if (x-2 >= 0 && y+1 < m && check[x-2][y+1] == -1) {
 55             check[x-2][y+1] = cnt+1;
 56             p2.x = x-2;
 57             p2.y = y+1;
 58             q.push(p2);
 59         }
 60         if (x+1 < n && y-2 >= 0 && check[x+1][y-2] == -1) {
 61             check[x+1][y-2] = cnt+1;
 62             p2.x = x+1;
 63             p2.y = y-2;
 64             q.push(p2);
 65         }
 66         if (x+2 < n && y-1 >= 0 && check[x+2][y-1] == -1) {
 67             check[x+2][y-1] = cnt+1;
 68             p2.x = x+2;
 69             p2.y = y-1;
 70             q.push(p2);
 71         }
 72         if (x-1 >= 0 && y-2 >= 0 && check[x-1][y-2] == -1) {
 73             check[x-1][y-2] = cnt+1;
 74             p2.x = x-1;
 75             p2.y = y-2;
 76             q.push(p2);
 77         }
 78         if (x-2 >= 0 && y-1 >= 0 && check[x-2][y-1] == -1) {
 79             check[x-2][y-1] = cnt+1;
 80             p2.x = x-2;
 81             p2.y = y-1;
 82             q.push(p2);
 83         }
 84     }
 85     return check[t.x][t.y];
 86 }
 87
 88 class CollectingRiders {
 89 public:
 90
 91 int minimalMoves(vector <string> board)
 92 {
 93     int i, j, k, l;
 94     int cnt, r, min1, fl;
 95     POINT p1, p2;
 96
 97     n = board.size();
 98     m = board[0].size();
 99     for (i = 0; i < n ;i++) {
100         strcpy(b[i], board[i].c_str());
101     }
102
103     for (i = 0; i < n; i++) {
104         for (j = 0; j < m; j++) {
105             for (k = 0; k < n; k++) {
106                 for (l = 0; l < m; l++) {
107                     p1.x = i;
108                     p1.y = j;
109                     p2.x = k;
110                     p2.y = l;
111
112                     cnt = bfs(p1, p2);
113                     map[i][j][k][l] = cnt;
114 //printf("map[%d][%d][%d][%d] = %d\n", i, j, k, l, cnt);
115                 }
116             }
117         }
118     }
119
120     // (k, l)의 rider를 (i, j)로 이동..
121     min1 = 999999999;
122     for (i = 0; i < n; i++) {
123         for (j = 0; j < m; j++) {
124             fl = 1;
125             cnt = 0;
126             for (k = 0; k < n; k++) {
127                 for (l = 0; l < m; l++) {
128                     if (b[k][l] != '.') {
129                         r = b[k][l] - '0';
130                         if (map[i][j][k][l] == -1) {
131                             fl = 0;
132                             break;
133                         }
134                         if (map[i][j][k][l] % r == 0)
135                             cnt += (map[i][j][k][l] / r);
136                         else
137                             cnt += (map[i][j][k][l] / r) + 1;
138                     }
139                 }
140                 if (fl == 0)
141                     break;
142             }
143
144             if (fl && cnt < min1)
145                 min1 = cnt;
146         }
147     }
148 printf("min1 = %d..\n", min1);
149     if (min1 == 999999999)
150         return -1;
151     return min1;
152 }
153
154 };




[1000] CharmingTicketsEasy

more..



to be updated..





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

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 SRM 383 Div 2 (완료)  (0) 2007.12.14
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
TopCoder SRM375 DIV2 (Complete)  (6) 2007.11.11

Comments

  1. 김우현 2007.12.14 07:55 Permalink Modify/Delete Reply

    저는 탑코더 후기로 채워지는 블로그가 좋은데요.. >_<;;; 으하핫;

    SRM 383에서 선방하신거 축하드려요~!
    저는 참가하려했는데 알고나니 이미 시간이 지났다는 ㅠ_ㅠ;;

Leave a Comment


to Top