TCO08 퀄 3라운드 문제를 연습삼아 풀어보았다..
이번 3라운드는 매치도중 시스템이 다운되는바람에 한번 더 열렸다.. -_-;;
그로인해 손해본사람도 있고.. 땡잡은사람도 있고.. ㅋㅋㅋㅋ

다행히 두개 다 연습세션에 추가되었다.. 먼저 열린게 Q3A, 나중에 열린게 Q3..
퀄 라운드 500점짜리는 죄다 DP문제의 연속이었다.. 우웩!!!!!!!!
그러다 마지막에 열린 매치는 DP문제가 떨어졌는지.. 다른 유형의 문제가 나왔다..
어떻게 하루만에 문제를 만들고 테스트케이스까지 만들수 있는지..;; 예비문제를 미리 준비하고있었나..?
아니면 Online Round1에 나올문제가 미리..?? 그렇담 좀 아쉬운데..;;;



[500] RandomNetwork
input으로 임의의 graph가 주어진다.. 0번 노드에서 packet을 전송할때 nstep 이후에 각 노드에 packet이 위치할 확률을 구하는 문제..

전형적인 DP문제이다..
음.. 은퇴한 이후에 감이 많이 떨어진것같다..(뭐 원래 못하긴했지만) 특히나 DP는 도저히 모르겠다.. ㅠ_ㅠ
DPDPDPDPDPDPDPDPDPDPDPDPDP.... 젠장젠장젠장젠장젠장젠장젠장젠장....


다음과 같은 점화식을 세울 수 있다..

dp[i][j] = i번 step에 packet이 j 위치에 있을 확률이라고 한다면..
dp[0][0] = 1.0
dp[i][j] = sum(dp[i-1][k] / (vertex k의 outdegree)) (k는 0 <= k < n 이고 k->j 의 edge가 있을때)

별로 어렵지않은 문제인데.. 열라 삽질끝에.. 293.33 점에 간신히 submit..! -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class RandomNetwork {
  9 public:
 10
 11 vector <double> probableLocation(vector <string> network, int steps)
 12 {
 13     int graph[100][100];
 14     int n;
 15     int i, j, k, l, cnt;
 16     char buf[100];
 17     double dp[200][200];
 18     vector<double> res;
 19
 20     n = network.size();
 21     memset(graph, 0, sizeof(graph));
 22
 23     for (i = 0; i < n; i++) {
 24         strcpy(buf, network[i].c_str());
 25         for (j = 0; j < n; j++) {
 26             if (buf[j] == 'Y') {
 27                 graph[i][j] = 1;
 28             }
 29         }
 30     }
 31
 32     memset(dp, 0, sizeof(dp));
 33     dp[0][0] = 1.0;
 34     for (i = 1; i <= steps; i++) {
 35         for (j = 0; j < n; j++) {
 36             for (k = 0; k < n; k++) {
 37                 cnt = 0;
 38                 for (l = 0; l < n; l++) {
 39                     if (graph[k][l])
 40                         cnt++;
 41                 }
 42                 if (graph[k][j]) {
 43                     dp[i][j] += dp[i-1][k] / (double)cnt;
 44                 }
 45             }
 46         }
 47     }
 48     for (i = 0; i < n; i++) {
 49         res.push_back(dp[steps][i]);
 50 printf("..%lf\n", dp[steps][i]);
 51     }
 52     return res;
 53 }
 54
 55 };




[500] CableDonation
각 room을 연결하는 chain의 길이가 주어진다.. 모든 room이 연결된 상태를 유지하기위해 뺄수있는 chain의 길이의 합을 최대화하는 문제..

별다른 응용이 없는 단순 MST 문제이다.. -_-;;

매치도중 많은사람들이 fail했는데.. 아마도 문제파악을 잘 못하고 greedy 접근방법으로 시도한 것 같다..
접근방법만 잘 찾았다면 쉽게 풀수 있었을듯..

나는 그냥 내꺼 MST 라이브러리 갖다 붙이고.. 조금 코딩해서 submit하니깐.. 411.97 점..
 
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <vector>
  6 using namespace std;
  7
  8 typedef struct _edge {
  9     int v1, v2;
 10     int dist;
 11 } EDGE;
 12 EDGE edge[1000000];
 13 int union_no[1000];
 14 int edge_cnt, n;
 15
 16 int comp(const void* a, const void* b)
 17 {
 18     EDGE* x, *y;
 19     x = (EDGE*)a;
 20     y = (EDGE*)b;
 21     if (x->dist < y->dist)
 22         return -1;
 23     else if (x->dist > y->dist)
 24         return 1;
 25     return 0;
 26 }
 27 int union_find(int u)
 28 {
 29     int temp = u;
 30     while (union_no[temp] != temp)
 31         temp = union_no[temp];
 32     return temp;
 33 }
 34
 35 class CableDonation
 36 {
 37 public:
 38
 39 int cable(vector <string> lengths)
 40 {
 41     int i, j;
 42     char buf[1000];
 43     int r1, r2;
 44     int sum, cnt;
 45     n = lengths.size();
 46
 47     for (i = 1; i <= n; i++) {
 48         union_no[i] = i;
 49     }
 50
 51     edge_cnt = 0;
 52     sum = 0;
 53     for (i = 0; i < n; i++) {
 54         strcpy(buf, lengths[i].c_str());
 55         for (j = 0; j < n; j++) {
 56             if (buf[j] == '0')
 57                 continue;
 58             else if (buf[j] >= 'a' && buf[j] <= 'z') {
 59                 edge[edge_cnt].v1 = i;
 60                 edge[edge_cnt].v2 = j;
 61                 edge[edge_cnt].dist = buf[j] - 'a' + 1;
 62                 sum += edge[edge_cnt].dist;
 63             }
 64             else {
 65                 edge[edge_cnt].v1 = i;
 66                 edge[edge_cnt].v2 = j;
 67                 edge[edge_cnt].dist = buf[j] - 'A' + 27;
 68                 sum += edge[edge_cnt].dist;
 69             }
 70             edge_cnt++;
 71         }
 72     }
 73     qsort(edge, edge_cnt, sizeof(EDGE), comp);
 74     cnt = 0;
 75     for (i = 0; i < edge_cnt; i++) {
 76         r1 = union_find(edge[i].v1);
 77         r2 = union_find(edge[i].v2);
 78         if (r1 == r2)
 79             continue;
 80         else if (r1 > r2)
 81             union_no[r2] = r1;
 82         else
 83             union_no[r1] = r2;
 84         cnt++;
 85         sum -= edge[i].dist;
 86     }
 87     if (cnt != n-1)
 88         return -1;
 89     return sum;
 90 }
 91
 92 };




나같은경우 Q1에서 통과하는바람에 Q2, Q3은 참여를 못했는데..
Q2랑 Q3은 Q1과 다르게 상당히 많은 contestant가 참여했고.. 완전 피튀기는 전쟁이었다..

내일 Online Round가 시작된다..
어휴.. 완전 ㅎㄷㄷㄷ 이던데.. 과연 잘할수있을까.. ;;;;

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

TopCoder SRM 394 Div 1  (2) 2008.03.24
흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27
TopCoder TCO08 Online Round 1  (2) 2008.02.17
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 388 Div1  (2) 2008.01.16
TopCoder SRM 387 Div1  (4) 2008.01.10

to Top