## TopCoder SRM 408 Div 1

Problem Solving/TopCoder logs 2008.07.03 22:15

화요일 저녁 8시에 열렸던 매치.. 이번에는 한번 두문제 풀어보나 했지만.. 역시 실패했다.. ㅠ_ㅠ 가까스로 서밋까지는 했는데.. 어이없는 케이스에 챌당했다..;; 흠.. 예전에는 이런 케이스에는 안당했는데..;; 어쨋든 문제가 트리키에서 여러명 fail하고.. 덕분에 rating도 약간 올랐다.. 현재 1353점으로.. 탑코더 전체 rated member 9529명중에 2008등을 달리고있다.. -_- 음.. 그래도 2008년에 2008등 한번 해보네..

Level1 - OlympicCandles

초가 여러개 있고 각각의 초의 길이가 주어진다.. 첫날은 촛불을 하나 켜야하고 둘째날은 두개를 켜야하고.. 등등이다.. 하루에 초는 1cm씩 탈때 최대 몇일동안 촛불을 켤수 있을까?

그냥 greedy 하게 풀었다.. 무조건 가장 킨 초를 사용하여 불을 켜고.. 초의 개수가 모자를때 break..

구현은 일단 가장 큰 값 k개를 뽑아내고 그 값을 변경후 다시 넣어야하므로.. heap 비스무리한 자료구조인 multiset을 쓰려고하였으나.. 생각해보니 초의 총 개수가 50밖에 안되므로 그냥 매번 sort했다..;;

1 #include <iostream>

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <set>

7 using namespace std;

8

9 class OlympicCandles {

10 public:

11

12 int numberOfNights(vector <int> candles)

13 {

14 int n, cnt;

15 int i, j;

16 multiset<int> c;

17 multiset<int>::iterator it;

18 cnt = 1;

19 while (1) {

20 sort(candles.begin(), candles.end());

21 n = candles.size();

22 if (n < cnt)

23 break;

24 for (i = n-1, j = 0; j < cnt; i--, j++) {

25 if (candles[i] <= 0)

26 break;

27 candles[i] -= 1;

28 }

29 if (j < cnt)

30 break;

31 cnt++;

32 }

33 return cnt-1;

34 }

35

36 };

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <set>

7 using namespace std;

8

9 class OlympicCandles {

10 public:

11

12 int numberOfNights(vector <int> candles)

13 {

14 int n, cnt;

15 int i, j;

16 multiset<int> c;

17 multiset<int>::iterator it;

18 cnt = 1;

19 while (1) {

20 sort(candles.begin(), candles.end());

21 n = candles.size();

22 if (n < cnt)

23 break;

24 for (i = n-1, j = 0; j < cnt; i--, j++) {

25 if (candles[i] <= 0)

26 break;

27 candles[i] -= 1;

28 }

29 if (j < cnt)

30 break;

31 cnt++;

32 }

33 return cnt-1;

34 }

35

36 };

Level2 - CandyGame

undirected acylic graph가 주어진다.. 임의의 vertex에 여러개의 캔디가 있을때 그 중 2개를 집어서 하나는 먹고 하나는 이웃한 (edge로 연결된) vertex로 보낼 수 있다. 이런식으로 해서 최적의 전략으로 주어진 target vertex에 캔디를 최소 한개 놓고싶다.. 이때 target vertex에 캔디를 놓지 못하게 하면서 최대로 많이 캔디를 몇개너 놓을수 있을까? 답이 20억이 넘으면 -1 return

아쉽게 풀지 못했다.. DFS 탐색하면서 해당하는 값을 찾는 방식으로 접근했는데.. 솔루션에 문제가 있었나보다.. 그리고 connected component가 아니면 답은 -1이다.. 어처구니없게도 챌 당했다.. -_-;

editorial을 참조하여 풀었다.. 우선 target을 제외한 모든 노드에 캔디 하나씩 놓는다.. 더 이상 캔디를 추가하면 target에 도달하는 조건이 만족한다.. 이 상태에서 각 캔디를 target과 가장 먼 노드로 다 밀어버린다.. 길이 n을 이동하려면 캔디가 2^n 개 필요하다는 것은 쉽게 생각해낼 수 있다.. 참 신선한 문제이군..

1 #include <iostream>

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 using namespace std;

7 #define max(x, y) ((x) > (y) ? (x) : (y))

8

9 int map[100][100];

10 int depth[100];

11 int n;

12

13 void dfs(int u, int len)

14 {

15 int i;

16 depth[u] = len;

17 for (i = 0; i < n; i++) {

18 if (map[u][i] && depth[i] == -1) {

19 dfs(i, len+1);

20 }

21 }

22 }

23

24 int max_depth(int u)

25 {

26 int i, r, max1;

27 max1 = depth[u];

28 for (i = 0; i < n; i++) {

29 if (map[u][i] && depth[i] > depth[u]) {

30 r = max_depth(i);

31 if (r > max1)

32 max1 = r;

33 }

34 }

35 return max1;

36 }

37

38 class CandyGame {

39 public:

40

41 int maximumCandy(vector <string> graph, int target)

42 {

43 int i, j, k;

44 long long sum;

45 n = graph.size();

46 if (n == 1)

47 return 0;

48 memset(map, 0, sizeof(map));

49 for (i = 0; i < n; i++) {

50 for (j = 0; j < n; j++) {

51 if (graph[i][j] == 'Y')

52 map[i][j] = 1;

53 }

54 }

55 memset(depth, -1, sizeof(depth));

56 dfs(target, 0);

57 for (i = 0; i < n; i++) {

58 if (depth[i] == -1)

59 break;

60 }

61 if (i != n)

62 return -1;

63 sum = 0;

64 for (i = 0; i < n; i++) {

65 if (i == target)

66 continue;

67 k = max_depth(i);

68 sum += 1LL << (max_depth(i) - depth[i]);

69 if (sum > 2000000000)

70 return -1;

71 }

72 return (int)sum;

73 }

74

75 };

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 using namespace std;

7 #define max(x, y) ((x) > (y) ? (x) : (y))

8

9 int map[100][100];

10 int depth[100];

11 int n;

12

13 void dfs(int u, int len)

14 {

15 int i;

16 depth[u] = len;

17 for (i = 0; i < n; i++) {

18 if (map[u][i] && depth[i] == -1) {

19 dfs(i, len+1);

20 }

21 }

22 }

23

24 int max_depth(int u)

25 {

26 int i, r, max1;

27 max1 = depth[u];

28 for (i = 0; i < n; i++) {

29 if (map[u][i] && depth[i] > depth[u]) {

30 r = max_depth(i);

31 if (r > max1)

32 max1 = r;

33 }

34 }

35 return max1;

36 }

37

38 class CandyGame {

39 public:

40

41 int maximumCandy(vector <string> graph, int target)

42 {

43 int i, j, k;

44 long long sum;

45 n = graph.size();

46 if (n == 1)

47 return 0;

48 memset(map, 0, sizeof(map));

49 for (i = 0; i < n; i++) {

50 for (j = 0; j < n; j++) {

51 if (graph[i][j] == 'Y')

52 map[i][j] = 1;

53 }

54 }

55 memset(depth, -1, sizeof(depth));

56 dfs(target, 0);

57 for (i = 0; i < n; i++) {

58 if (depth[i] == -1)

59 break;

60 }

61 if (i != n)

62 return -1;

63 sum = 0;

64 for (i = 0; i < n; i++) {

65 if (i == target)

66 continue;

67 k = max_depth(i);

68 sum += 1LL << (max_depth(i) - depth[i]);

69 if (sum > 2000000000)

70 return -1;

71 }

72 return (int)sum;

73 }

74

75 };

Level3 - TournamentSeeding

to be updated..

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

TopCoder SRM 414 Div 1 (0) | 2008.08.17 |
---|---|

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 407 Div 1 (2) | 2008.06.28 |

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 |