두번째 시도한 SRM.. 사실 SRM362 결과가 취소되면서 첫번째 시도인거나 마찬가지다..
근데 어처구니없게도 uva에있는 문제와 거의 똑같은 문제가 나오면서..
한문제를 거저먹었다.. 덕분이 방 1등, 전체 32등.. -_-;
지금 실력에 비해 rating이 너무 높아서 걱정이다..;;

사용자 삽입 이미지


 
[250] MirroredClock

거울에 반사된 시계의 시간을 보고 실제 시간 구하기..
그냥 조금만 생각해보면 된다..;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class MirroredClock {
      9 public:
     10
     11 string whatTimeIsIt(string time)
     12 {
     13     char buf[10];
     14     int a, b, c, d;
     15     string ret;
     16     strcpy(buf, time.c_str());
     17     sscanf(buf, "%d:%d", &a, &b);
     18
     19     d = 60 - b;
     20     c = 12 - a;
     21     if (d > 0 && d < 60)
     22         c--;
     23     if (c == 12)
     24         c = 0;
     25     if (d == 60)
     26         d = 0;
     27     sprintf(buf, "%02d:%02d", c, d);
     28     ret = buf;
     29     return ret;
     30 }
     31
     32 };






[500] HandsShaking

원탁에 사람들이 앉아있고 동시에 악수를 하는데 각각의 팔이 cross 되지 않아야 한다.
악수를 할 수 있는 경우의 수 구하기..

http://acm.uva.es/p/v9/991.html 
이문제와 똑같다.. -_-;;
위의 문제를 미리 풀어본 나는 덕분에 거져먹었다..

그런데 이 문제는 Catalan Number를 구하면 된다고 하더라.. 음.. 왜일까..
코드는 생략..

Catalan Number에 관한 글..
http://apnetwork.tistory.com/25


[1000] CrazyComponents


component들을 골라서 application을 만든다.. component를 선택하는것은 랜덤이고(-_-) 각 component끼리는 서로 dependency가 존재한다.. 그리고 각 component를 설치했을때의 설치비용과 수익이 주어진다..
최대 얻을수있는 수익을 구하는 문제..

첫번째 파라미터 k는 k개의 component를 선택
두번째 파라미터는 각 component간의 dependency
세번째 파라미터는 수익
네번째 파라미터는 설치비용..

어떻게 풀어야하나.. ㅠ_ㅠ


다른 사람들 소스를 보고나서야 겨우 이해했다..
역시 고수들은 다르군..
소스를 보니 pure dp로 푼사람도 있었지만.. 대체로 recursion + memorization으로 구현했다..

k번째 단계에서 i번째 component를 선택하는경우와 선택하지않는경우중 더 이익이 남는쪽을 선택한다..
어느쪽이 더 이익인지 알기 위해서는 k-1단계에서 i번째를 선택했을때와 선택하지않았을때를 비교해서 알 수 있다..
즉, 이러한 방법으로 recursive로 계산을 해야한다..
단, 같은상태에대해서 여러번 계산하지 않기위해 memorization을 해야한다..

아.. 어렵다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 using namespace std;
      6 #define max(x, y) ((x) > (y) ? (x) : (y))
      7
      8 class CrazyComponents {
      9 public:
     10
     11 int n;
     12 int pro[15];
     13 int need[15];
     14 char check[51][1<<15];
     15 double dp[51][1<<15];
     16
     17 double recur(int k, int mask)
     18 {
     19     int i;
     20     double res;
     21     if (check[k][mask])
     22         return dp[k][mask];
     23     check[k][mask] = 1;
     24     if (k == 0) {
     25         dp[k][mask] = 0.0;
     26         return 0.0;
     27     }
     28     res = 0.0;
     29     for (i = 0; i < n; i++) {
     30         if ((need[i] & mask) == need[i]) {
     31             res += max(recur(k-1, mask), (double)pro[i]+recur(k-1, mask|(1<<i)));
     32         }
     33         else {
     34             res += recur(k-1, mask);
     35         }
     36     }
     37     res /= n;
     38     dp[k][mask] = res;
     39     return res;
     40 }
     41
     42 double expectedProfit(int k, vector<string> components, vector<int> income, vector<int> expense) {
     43     int i;
     44     char buf[1000];
     45     char* p;
     46     n = components.size();
     47     memset(need, 0, sizeof(need));
     48     for (i = 0; i < n; i++) {
     49         strcpy(buf, components[i].c_str());
     50         p = strtok(buf, " ");
     51         while (p != NULL) {
     52             need[i] |= (1 << atoi(p));
     53             p = strtok(NULL, " ");
     54         }
     55         pro[i] = income[i]-expense[i];
     56     }
     57     memset(dp, 0, sizeof(dp));
     58     memset(check, 0, sizeof(check));
     59     return recur(k, 0);
     60 }
     61
     62 };

'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