TopCoder SRM 407 Div 1

Problem Solving/TopCoder logs 2008. 6. 28. 00:12
밤 12시에 열렸던 매치.. 평소에 비해서 문제는 약간 쉬웠는데 아쉽게도 한문제밖에 못풀었다.. 250 & 500 둘다 그다지 안어려운 문제였는데.. 250은 문제 이해하는데 시간낭비하고.. 500은 전혀 엉뚱한곳에서 삽질하다가..  종료 10분전에 솔루션이 떠올랐다.. 젠장.. 평소에비해서 두문제 이상 푼 사람이 좀 많았던 매치.. 덕분에 rating은 하락 했다.. ㅠ_ㅠ 결국 rating 3연속 상승에서 마감.. Div 1은 왜이리 힘든것이야..!! ㅠ_ㅠ


사용자 삽입 이미지



Level1 - CorporationSalary
어느 회사에서 자신의 부하직원이 아무도 없는 사람은 월급이 1이다. 그 이외의 사람의 월급은 그사람의 직속 부하직원의 월급의 합이다. 이때 회사 전체 사람의 월급의 합을 구하기

간단하게 DFS + memorization으로 해결.. 요즘 이런 유형이 자주 나오는거 같다.. 현재 노드에 대해서 자식 노드의 월급의 합을 구해서 그 합을 더한다.. 자식 노드에 대해서도 같은 방법을 적용하여 재귀적으로 구하고.. 자식이 없는 노드는 문제 조건에 따라 1을 리턴..

처음에 문제를 잘못이해하고.. 어떤사람의 직 간접적으로 부하인 사람의 월급의 모든 합을 구해야하는줄 알았다.. 그래서 Floyd 알고리즘을 사용하여 transitive closure를 구했는데.. sample이 안나온다.. OTL .. -_- 그래서 Floyd 부분을 제거하고 돌려보니 OK.. 그래서 그냥 서밋했다.. 덕분에 시간좀 까먹었다.. ㅎㅎ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 long long memo[100];
  9 int graph[100][100];
 10 int deg[100];
 11 int n;
 12
 13 long long dfs(int u)
 14 {
 15     int i;
 16     long long sum;
 17     if (memo[u] != 0)
 18         return memo[u];
 19     if (deg[u] == 0)
 20         return memo[u] = 1;
 21     sum = 0;
 22     for (i = 0; i < n; i++) {
 23         if (graph[u][i])
 24             sum += dfs(i);
 25     }
 26     return memo[u] = sum;
 27 }
 28
 29 class CorporationSalary {
 30 public:
 31
 32 long long totalSalary(vector <string> relations)
 33 {
 34     int i, j, k;
 35     long long sum;
 36     char buf[100];
 37     n = relations.size();
 38     memset(graph, 0, sizeof(graph));
 39     memset(deg, 0, sizeof(deg));
 40     for (i = 0; i < n; i++) {
 41         strcpy(buf, relations[i].c_str());
 42         for (j = 0; j < n; j++) {
 43             if (buf[j] == 'Y')
 44                 graph[i][j] = 1;
 45         }
 46     }/*
 47     for (k = 1; k < n; k++) {
 48     for (i = 1; i < n; i++) {
 49     for (j = 1; j < n; j++) {
 50         if (graph[i][k] && graph[k][j])
 51             graph[i][j] = 1;
 52     }
 53     }
 54     }*/
 55     for (i = 0; i < n; i++) {
 56         for (j = 0; j < n; j++) {
 57             if (graph[i][j])
 58                 deg[i]++;
 59         }
 60     }
 61     memset(memo, 0, sizeof(memo));
 62     for (i = 0; i < n; i++) {
 63         if (memo[i] == 0) {
 64             dfs(i);
 65         }
 66     }
 67     sum = 0;
 68     for (i = 0; i < n; i++) {
 69         sum += memo[i];
 70     }
 71     return sum;
 72 }
 73
 74 };



Level2 - PointsGame

n개의 점이 X-Y 좌표로 주어진다. 두 사람이 선택 안된 점들을 하나씩 번갈아가면서 선택한다. 서로 다른 사람이 선택한 점끼리 이은 선분의 합을 첫번째 사람은 최대화 하려고 하고 두번째 사람은 최소화 하려고 한다.. 결국 모든 선분의 합은 얼마가 될까..?

s1 = 첫번째 사람이 선태한 점들
s2 = 두번째 사람이 선택한 점들
side = 현재 누구차례?

를 상태공간으로 해서 구한다.

점들의 set 을 나타낼때 1번이 선택했는지, 2번이 선택됐는지, 선택 안됐는지 3가지 상태로 나눠지는데..
이는 코딩하기가 까다롭다.. 그래서 map 을 이용해서 처리..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 #include <map>
  8 using namespace std;
  9 //#define min(x, y) ((x) > (y) ? (y) : (x))
 10 //#define max(x, y) ((x) > (y) ? (x) : (y))
 11 //#define INF 999999999
 12 //#define EPS 1e-14
 13
 14 typedef struct _d {
 15     int s1, s2;
 16 } DATA;
 17
 18 double dist[15][15];
 19 int n;
 20 map<DATA, double> mm;
 21
 22 bool operator< (const DATA& a, const DATA& b)
 23 {
 24     if (a.s1 != b.s1)
 25         return a.s1 < b.s1;
 26     return a.s2 < b.s2;
 27 }
 28
 29 double get_dist(double x1, double y1, double x2, double y2)
 30 {
 31     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 32 }
 33
 34 int is_subset(int s1, int s2)
 35 {
 36     if ((s1 & s2) == s2)
 37         return 1;
 38     return 0;
 39 }
 40
 41 double recur(int s1, int s2, int side)
 42 {
 43     int i, j;
 44     double sum, res;
 45     double temp;
 46     DATA d1;
 47     d1.s1 = s1;
 48     d1.s2 = s2;
 49     if (mm.find(d1) != mm.end()) {
 50         return mm[d1];
 51     }
 52     if (s1 + s2 == (1<<n) - 1) {
 53         sum = 0;
 54         for (i = 0; i < n; i++) {
 55             for (j = 0; j < n; j++) {
 56                 if (is_subset(s1, (1<<i)) && is_subset(s2, (1<<j))) {
 57                     sum += dist[i][j];
 58                 }
 59             }
 60         }
 61         mm[d1] = sum;
 62         return sum;
 63     }
 64     if (side == 0)
 65         res = -1e100;
 66     else
 67         res = 1e100;
 68     for (i = 0; i < n; i++) {
 69         if (!is_subset(s1, (1<<i)) && !is_subset(s2, (1<<i))) {
 70             temp = recur(s2, s1|(1<<i), 1-side);
 71             if (side == 0) {
 72                 if (temp > res)
 73                     res = temp;
 74             }
 75             else {
 76                 if (temp < res)
 77                     res = temp;
 78             }
 79         }
 80     }
 81     mm[d1] = res;
 82     return res;
 83 }
 84
 85 class PointsGame {
 86 public:
 87
 88 double gameValue(vector <int> pointsX, vector <int> pointsY)
 89 {
 90     int i, j;
 91     double res;
 92     n = pointsX.size();
 93     for (i = 0; i < n; i++) {
 94         for (j = 0; j < n; j++) {
 95             dist[i][j] = get_dist(pointsX[i], pointsY[i], pointsX[j], pointsY[j]);
 96         }
 97     }
 98     mm.clear();
 99     res = recur(0, 0, 0);
100     return res;
101 }
102
103 };






Level3 - TransformMatrix



to be updated..

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

TopCoder SRM 413 Div 1  (0) 2008.08.08
TopCoder SRM 412 Div 1  (0) 2008.08.01
TopCoder SRM 410 Div 1  (2) 2008.07.20
TopCoder SRM 409 Div 1 (완료)  (0) 2008.07.11
TopCoder SRM 408 Div 1  (0) 2008.07.03
TopCoder SRM 405 Div 1  (2) 2008.06.15
TopCoder SRM 404 Div 1  (2) 2008.06.06
TopCoder SRM 402 Div 1  (0) 2008.05.25
TopCoder SRM 401 Div1  (2) 2008.05.07
TopCoder SRM 400 Div 1  (0) 2008.05.02
  • By helloneo

to Top

티스토리툴바