일주일만에 참여한 SRM.. 역시.. 아침11시는 너무 힘들다.. ㅠ_ㅠ 집중력이 아무래도 저녁시간과 틀린것같아.. ㅠ_ㅠ 특히 250 문제읽는 중 연구실 모 선배님과의 면담으로인해 많은시간을 까먹고.. 결국 문제 포기상태에 이르렀다.. ㅠ_ㅠ rating은 아주 쬐금 올랐다.. 목표였던 r 1000은 실패.. ㅠ_ㅠ;; 250점은 남들 다 풀었는데.. 왜 나만 못푼것인가.. 그리고 역시.. 난 챌을 시도하면 안돼.. ㅠ_ㅠ;;;

방 5등 전체 167등..

사용자 삽입 이미지

사용자 삽입 이미지
그래도 사상 처음으로 세번 연속 올랐군..




[250] DownloadingFiles
여러개의 task가 주어지고.. 각각의 task는 bandwidth와 걸리는시간의 쌍으로 주어진다.. 하나의 task가 끝나면 그동안 쓰고있던 bandwidth가 free가 되고.. 다음 작업에 더해서 쓸수있다.. 쉽게생각하면 여러개의 파일을 동시에 다운받을때.. 예상시간이나오고.. 하나 다운로드가 끝나면.. 다른파일들 예상시간이 팍 줄어드는.. 뭐 그런효과라 하겠다..

흠.. 꼭 풀었어야했는데 아쉽게 놓쳤다.. 초반에 문제 이해하는데도 오래걸렸고.. 중간에 인터럽트로인해 시간도 좀 까먹고.. 결국 시간에 쫒겨서 제대로 시도하지도 못했다..  안타깝다.. 나의 실력이 정말 이거밖에 안되는것인가.. ㅠ_ㅠ

있는 그대로 코딩하는 방법 말고.. 뭔가 꽁수가 반드시 존재할거라고 생각했는데.. 결국 찾는데 실패.. 나중에 다른사람 코드를 보고나서야 깨달았다.. 이런 제길 ㅠ_ㅠ;;; 어쨋든.. 좋은문제이다..

task를 동시에 실행하든 일렬로 실행하든 상관이 없다.. 따라서 총 bandwidth를 구하고 총 task의 크기를 구해서 그것을 한번에 계산하면 된다..

"거리 = 속력 * 시간" (이런 기초 공식을 알고도 못써먹다니..)

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class DownloadingFiles {
      9 public:
     10
     11 double actualTime(vector <string> tasks)
     12 {
     13     int n, i;
     14     char buf[100];
     15     double size, sp, ti, sum;
     16     n = tasks.size();
     17     size = sum = 0;
     18     for (i = 0; i < n; i++) {
     19         strcpy(buf, tasks[i].c_str());
     20         sscanf(buf, "%lf %lf", &sp, &ti);
     21         size += sp * ti;
     22         sum += sp;
     23     }
     24     return size / sum;
     25 }
     26
     27 };




[500] SellingProducts
input으로 price와 cost가 들어온다.. price는 소비자가 살수있는 가격.. cost는 그 소비자에게 팔때 드는 배송비용이다.. 소비자가 원하는가격보다 더 싸게 가격을 책정에도 물론 소비자는 산다.. 그러나 배송비용이 더 많이들어서 전혀 이득이 없으면 그 소비자에게는 안팔아도 된다.. 이때 최대의 이익을 내기위한 가격을 구하는문제..

비교적 쉬운문제이다.. 오히려 250보다 더 쉬운데.. 흠.. 사람들은 반대였던것같다..

처음에 가격순으로 정렬한 후 1차원 maximum sum을 돌릴까.. 생각하다가.. 다시보니 input size가 최대50이다.. 그래서 고민하지 않고 모든가격에대해 다 비교해보았다.. O(n^2)

챌 phase 막판에 뭔가 번뜩 떠올라 급조해서 테스트케이스를 만들었는데.. 2번시도해서 다 실패했다.. 알고보니 테스트케이스를 잘못만들었다.. ㅠ_ㅠ;;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class SellingProducts {
      9 public:
     10
     11 int optimalPrice(vector <int> price, vector <int> cost)
     12 {
     13     int i, j;
     14     int n;
     15     int max1, sum, sell;
     16     max1 = sell = 0;
     17     n = price.size();
     18     for (i = 0; i < n; i++) {
     19         sum = 0;
     20         for (j = 0; j < n; j++) {
     21             if (price[j] >= price[i]) {
     22                 if (price[i] - cost[j] > 0) {
     23                     sum += price[i]-cost[j];
     24                 }
     25             }
     26         }
     27 printf("i = %d, sum = %d\n", i, sum);
     28         if (sum > max1) {
     29             max1 = sum;
     30             sell = price[i];
     31         }
     32         else if (sum == max1) {
     33             if (sell > price[i]) {
     34                 sell = price[i];
     35             }
     36         }
     37     }
     38     return sell;
     39 }
     40
     41 };




[900] TVGameWinnings
n by n 보드가 주어지고 각 row당 & 각 col당 1개의 원소를 택한다.. 선택된 원소를 vertex라고 생각하고 (i, j)의 원소가 선택되었다고 하면, (i, j)는 (j, k) 원소와 edge로 연결된다.. 이런식으로 그래프를 구성하여 탐색할때 선택된 모든 vertex의 곱 * (-1)^(# of connected component % 2 + 1) 을 통해서 나올수 있는 값의 최소값과 최대값을 구하는 문제..

즉, 2 by 2 보드라고 생각하면
(0, 1) -> (1, 0) 이런 경우와
(0, 0), (1, 1) 이런 경우가 나올 수 있다..

문제 파악이 상당히 힘든 문제..;;


board size가 최대 6이므로 나올수 있는 모든 pair를 dfs을 통해서 다 찾는다..
찾은 pair에 대해서 graph를 구성하고 역시 dfs로 탐색하여 connected component의 개수를 구한다..
문제 파악이 가장 어려운 문제.. 해법은 그냥 brute force.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int b[10][10], path[10];
  9 int n, c, sum;
 10 char check[10], check2[10];
 11 int min1, max1;
 12
 13 void dfs2(int u)
 14 {
 15     if (check2[path[u]] == 0) {
 16         check2[path[u]] = 1;
 17         sum *= b[u][path[u]];
 18         dfs2(path[u]);
 19     }
 20 }
 21
 22 void dfs(int u)
 23 {
 24     int i;
 25     if (u == n) {
 26         memset(check2, 0, sizeof(check2));
 27         c = 0;
 28         sum = 1;
 29         for (i = 0; i < n; i++) {
 30             if (check2[path[i]] == 0) {
 31                 c++;
 32                 check2[path[i]] = 1;
 33                 sum *= b[i][path[i]];
 34                 dfs2(path[i]);
 35             }
 36         }
 37         if (c % 2 == 0)
 38             sum *= -1;
 39         if (sum < min1)
 40             min1 = sum;
 41         if (sum > max1)
 42             max1 = sum;
 43         return ;
 44     }
 45     for (i = 0; i < n; i++) {
 46         if (!check[i]) {
 47             check[i] = 1;
 48             path[u] = i;
 49             dfs(u+1);
 50             check[i] = 0;
 51         }
 52     }
 53 }
 54
 55 class TVGameWinnings {
 56 public:
 57
 58 vector <int> getMinMax(vector <string> board)
 59 {
 60     int i, j;
 61     char buf[10];
 62     vector<int> res;
 63
 64     n = board.size();
 65     for (i = 0; i < n; i++) {
 66         strcpy(buf, board[i].c_str());
 67         for (j = 0; j < n; j++) {
 68             if (buf[j] >= '0' && buf[j] <= '9') {
 69                 b[i][j] = buf[j] - '0';
 70             }
 71             else {
 72                 b[i][j] = -1 * (buf[j]-'A'+1);
 73             }
 74         }
 75     }
 76
 77     memset(check, 0, sizeof(check));
 78     memset(path, -1, sizeof(path));
 79     max1 = -999999999;
 80     min1 = 999999999;
 81     dfs(0);
 82     res.push_back(min1);
 83     res.push_back(max1);
 84     return res;
 85 }
 86
 87 };


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

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 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

to Top