정말 오래간만에 했던 SRM 결과는 참담.. -_- 뭐 굳이 변명을하자면.. 아침 10시라 잠이 좀 덜깼다는거..;; easy 부터 코딩 짜증나는게 나오면서.. 괜히 하기가 싫어졌다.. medium 문제가 재밌어보였는데.. 결국 해법을 못찾았다.. 막판에 다시 easy를 잡고 한문제라도 풀어보려고했지만.. compile error의 압박으로..;; topcoder는 C유저한테 너무 불리한거 아닌가..;;

 
사용자 삽입 이미지
한번에 300점이나 떨어지다니.. -_- DIV1 안해!!

[300] Paintball
easy 문제는..
paintball로 맞추는 게임을 하는데.. 각 팀과 팀에 속한 멤버 정보가 들어오고.. 상대방을 맞추면 개인점수가 올라가고 그에따라 팀점수도 올라간다.. 맞는 사람은 역시 개인 점수가 떨어지고 팀점수가 떨어진다.. 단, 같은편을 맞춘경우는 감점을 당한다..
팀순위 순으로 sort하고.. 각 팀 안에서는 member순으로 sort하는 문제..

시간이 5분만 더있었으면 submit은 할수있었는데.. -_-;


[500] PowerPlants

두번째 문제는 정전이 된 발전소를 모두 살리는 최소 비용을 구하는 문제이다.
input으로 2차원 배열이 들어오는데 i행 j열이 i번 발전소로 j번 발전소를 살리는데 드는 비용이다..
이어서 들어오는 string이 'Y'는 현재 동작하는 발전소 'N'는 현재 정전된 발전소라는 의미..

완전 난감.. -_-
TSP인거 같기도하고.. 생각해보니 아닌거같기도 하고.. 그냥 backtracking으로 시도해볼까 하다가 그냥 포기..;
현재 발전소 상태를 bit로 나타내서 그 상태까지의 최소비용을 저장해나가는 방식으로 어떻게 recursion, dp 등을 샤바샤바하면 될것같기도하다.. 다른사람 코드를 보면서 나중에 더 생각해봐야겠다..


문제를 잘못 이해했다..;;;; 발전소를 모두 살리는것이 아니라 numPlants개만 살아있으면 된다.. 따라서 처음 주어진 string에서 'Y'가 numPlants개 이상 있으면 답은 0 이다..
별다른 알고리즘이 없었다.. -_-;; 그냥 backtracking + memorization 문제였다.. 이렇게 쉬운문제를 못풀다니.. 아.. 한심스럽다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 #include <cctype>
      7 using namespace std;
      8 #define INF 999999999
      9 #define min(x, y) ((x) > (y) ? (y) : (x))
     10
     11 class PowerPlants {
     12 public:
     13
     14 int cost[20][20];
     15 int memo[1000000];
     16 int n;
     17 char p_stat[20];
     18
     19 int dfs(int mask, int cnt)
     20 {
     21     int i, j, min1;
     22
     23     if (memo[mask] >= 0) {
     24         return memo[mask];
     25     }
     26     if (cnt <= 0) {
     27         memo[mask] = 0;
     28         return 0;
     29     }
     30
     31     min1 = INF;
     32     for (i = 0; i < n; i++) {
     33         if (mask & (1 << i)) {
     34             for (j = 0; j < n; j++) {
     35                 if ((mask & (1<<j)) == 0) {
     36                     min1 = min(min1, dfs(mask | (1 << j), cnt-1) + cost[i][j]);
     37                 }
     38             }
     39         }
     40     }
     41     return (memo[mask] = min1);
     42 }
     43
     44 int minCost(vector<string> connectionCost, string plantList, int numPlants)
     45 {
     46     int i, j;
     47     int mask, cnt;
     48     char buf[100];
     49
     50     n = connectionCost.size();
     51     for (i = 0; i < n; i++) {
     52         strcpy(buf, connectionCost[i].c_str());
     53         for (j = 0; j < n; j++) {
     54             if (isdigit(buf[j])) {
     55                 cost[i][j] = buf[j] - '0';
     56             }
     57             else {
     58                 cost[i][j] = buf[j] - 'A' + 10;
     59             }
     60         }
     61     }
     62
     63     strcpy(p_stat, plantList.c_str());
     64     mask = cnt = 0;
     65     for (i = 0; i < n; i++) {
     66         if (p_stat[i] == 'Y') {
     67             mask |= (1 << i);
     68             cnt++;
     69         }
     70     }
     71     memset(memo, -1, sizeof(memo));
     72     return dfs(mask, numPlants-cnt);
     73 }
     74
     75
     76 };




[1000] YankeeSwap

아직 읽어보지 않았다.. 다른문제 다 풀어보고.. 시간있으면.. -_-

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

TopCoder SRM 371 Div2 (완료)  (2) 2007.10.14
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
TopCoder SRM 365 Div 1  (0) 2007.09.13
TopCoder SRM 364 Div 1  (0) 2007.09.09
TopCoder SRM 363 Div 2 (완료)  (0) 2007.08.12
TopCoder SRM 362 Div 2  (0) 2007.08.08
탑코더(TopCoder) 시작하기..  (0) 2007.08.07

Leave a Comment


to Top