## TopCoder SRM 386 Div 2

새벽 2시에 열린 매치.. 두문제를 안정적(?)으로 푼 덕분에 작년 9월 이후로 처음으로 blue로 복귀했다.. 휴우..; 역시.. 탑코더는 새벽 2시에 해야.. 등급이 오르는군..

방 3등 전체 51등.. 흠.. 500을 푸는데 좀 오래걸렸다.. 좀더 빨리풀수있었는데.. blue로 복귀.. 오랜만에 다시 1군에 올라간다.

 TrophyShelf
숫자들이 주어지고.. 각각은 trophy의 높이를 말한다.. 왼쪽에서 보았을때 보이는 trophy와 오른쪽에서 보았을때 보이는 trophy의 개수 구하기..

앞에서부터 읽어서 구하고 다시 뒤에서부터 읽으면서 구했다.. 별다른 알고리즘이 필요없는.. -_-;
나름대로 빨리 이해해서 코딩했는데.. 그래도 남들보다 많이 늦었다.. 다들 왜이리 코딩속도가 빠른겨..;;

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class TrophyShelf {
9 public:
10
11 vector <int> countVisible(vector <int> trophies)
12 {
13     int n, i;
14     int cnt1, cnt2, max1;
15     vector<int> res;
16     n = trophies.size();
17     cnt1 = 0;
18     max1 = -1;
19     for (i = 0; i < n; i++) {
20         if (max1 < trophies[i]) {
21             max1 = trophies[i];
22             cnt1++;
23         }
24     }
25     max1 = -1;
26     cnt2 = 0;
27     for (i = n-1; i >= 0; i--) {
28         if (max1 < trophies[i]) {
29             max1 = trophies[i];
30             cnt2++;
31         }
32     }
33     res.push_back(cnt1);
34     res.push_back(cnt2);
35     return res;
36 }
37
38 };

 CandidateKeys

DB에 해당하는 table이 주어지고 여러개의 attribute를 조합해서 superkey를 만들고 싶을때 어떻게 조합해야 하는지.. 이때 최대 크기의 candidate key와 최소 크기의 candidate key 구하기..
candidate key가 되기위한 조건은 attribute set의 subset이 candidate key가 되면 안된다..

흠.. 위의 설명이 맞는지 잘 모르겠다.. 오랜만에 DB때 배웠던 지식이 나왔는데 하나도 기억이 안나는군.. ㅠ_ㅠ
super key와 candidate key 등을 다시한번 찾아봐야겠다..

attr의 개수가 최대 10개밖에 안되므로.. 가능한 모든 subset을 다 구했다.. (2^m) 그래서 얻은 값이 key가 될수있는지 전쌍 비교를 통해 무식하게 판단 (n^2)하고.. key로 가능한 경우.. 이전에 구한 다른key들의 subset인지를 또 판단했다.. 그래서 최종적으로 통과한 key를 후보에 넣고.. attr의 개수의 최대, 최소를 구했다..

attr의 subset은 bit연산을 통하여 하나의 integer로 표현하였다..
다른사람의 솔루션도 다 비슷한 듯..

이문제 코딩하다가 코딩이 너무 짜증나서 그냥 때려치고 1000점 짜리 문제를 열고 해석했는데.. 앞으로 그런짓은 하지말아야겠다.. ㅠ_ㅠ 오히려 시간만 낭비한꼴이되었다..

음.. 참고로 이문제는 SRM 366 GuitarConcert 문제랑 푸는방법이 비슷한거같기도 하다..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 #define min(x, y) ((x) > (y) ? (y) : (x))
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 int check_subset(int u, int v)
11 {
12     if ((u & v) == v)
13         return 1;
14     return 0;
15 }
16
17 class CandidateKeys {
18 public:
19
20 vector <int> getKeys(vector <string> table)
21 {
22     int n, m, size;
23     int i, j, k, l;
24     int cnt, fl, bt;
25     int min1, max1;
26     char str;
27     char temp;
28     int candi;
29     vector<int> res;
30
31     n = table.size();
32     m = table.size();
33     for (i = 0; i < n; i++) {
34         strcpy(str[i], table[i].c_str());
35     }
36     size = (1 << m);
37     cnt = 0;
38     for (i = 1; i < size; i++) {
39         l = 0;
40         for (k = 0; (1<<k) <= i; k++) {
41             bt = (1 << k);
42             if (bt & i) {
43                 for (j = 0; j < n; j++) {
44                     temp[j][l] = str[j][k];
45                     temp[j][l+1] = 0;
46                 }
47                 l++;
48             }
49         }
50 //printf("i = %d\n", i);
51         fl = 1;
52         for (j = 0; j < n; j++) {
53             for (k = j+1; k < n; k++) {
54 //printf("temp[%d] = %s, temp[%d] = %s\n", j, temp[j], k, temp[k]);
55                 if (!strcmp(temp[j], temp[k])) {
56                     fl = 0;
57                     break;
58                 }
59             }
60         }
61         if (fl == 0) {
62             continue;
63         }
64         for (j = 0; j < cnt; j++) {
65             if (check_subset(i, candi[j]))
66                 break;
67         }
68         if (j == cnt)
69             candi[cnt++] = i;
70     }
71 /*
72 printf("cnt = %d\n", cnt);
73 for (i = 0; i < cnt; i++) {
74     printf("candi[%d] = %d\n", i, candi[i]);
75 }
76 */
77     res.clear();
78     if (cnt == 0)
79         return res;
80     min1 = 1000000;
81     max1 = -1;
82     for (i = 0; i < cnt; i++) {
83         k = 0;
84         for (j = 1; j <= candi[i]; j*=2) {
85             if (candi[i] & j) {
86                 k++;
87             }
88         }
89         min1 = min(min1, k);
90         max1 = max(max1, k);
91     }
92     res.push_back(min1);
93     res.push_back(max1);
94 printf("min1= %d, max1 = %d\n", min1, max1);
95     return res;
96 }
97
98 };

 LittleTree

tree가 주어진다.. 이 tree의 height를 height로 바꾸고싶을때 얼마의 비용이 드는지 구하는 문제.. U를 root로 하는 subtree를 떼어다 V의 자식으로 붙일때 드는 비용은 Level(V)-Level(U)-1 이다..

to be updated..

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

 TopCoder TCO08 Qualification Round 1  (4) 2008.02.06 2008.02.03 2008.01.25 2008.01.16 2008.01.10 2008.01.06 2007.12.30 2007.12.20 2007.12.14 2007.12.13 2007.12.09

### Comments

1. 김우현 2008.01.07 19:54

첫. DIV1이였는데... ㅠㅠ
250(DIV2 500)문제가 너무 어려웠어요 T-T;;;

• 2008.01.07 23:43 신고

음.. 긴장하셨나보네요.. ㅎㅎ 저도 div1 세번인가 했었는데.. 결국 한문제도 못풀었다는.. ㅠ_ㅠ

2. defihition 2008.01.08 16:20 신고

저도 이번에는 할려고 기다렸는데.. 막판에 까먹었어요 ㅠㅠ

• 2008.01.08 22:14 신고

음.. 다음매치는 목요일날 아침 11시에 있어.. ㅋㅋㅋ

to Top