TopCoder SRM 410 Div 1

어제 새벽 1시에 열렸던 매치.. 이번 매치에서는 어떻게 뽀록이 터지면서 역대 최고의 성적을 올렸다.. 방 1등 전체 147등.. Div2에서도 방 1등해본적이 거의 없는데 Div1에서 1등이라니..;; 허허.. 이번에 문제가 대박 어렵게 나와서.. 아예 코딩 시간에 문제 푸는걸 포기하고 챌 데이타를 준비한게 도움이 되었다.. -_-;;

1492로 역대 두번째 높은 raiting 획득.. 조금만 더 선전했으면 yellow 까지 올라갈수 있었는데.. 조금 모잘랐다..;; 한동안 div1과 div2 사이에서 불안한 행보를 했었는데.. 이제는 안정권인가..?

이번에도 엄청나게 많은 사람이 참여했다.. 새벽 1시임에도 불구하고 한국사람만 무려 47명이 참가했다.. 우아.. 덕분에 상당히 재미있는 매치가 되었다.. 같은방에서 xhae님도 만나고.. Div2에서는 nocut98님이 화재를 몰고다녔고.. 그리고 우리학교 출신 한명(Radient)이 Div1으로 승격되었다.. 앞으루 후배들이 많이 올라와야 할텐데 요즘애들은 그닥 열심히 준비하는 사람이 없어서 걱정스럽다..

사실 어제 후배들 따라서 엠티갈려고했는데.. 비가 너무많이와서.. 도저히 갈 엄두가 나지 않았다.. ㅠ_ㅠ 덕분에 탑코더를 참여할 수 있었지만.. 열심히 놀고있을 후배들 생각하니.. 아쉽기만하군.. ㅠ_ㅠ input으로 그래프가 주어진다.. 그래프의 각 노드는 electrical outlet (이하 O) 이거나, connection to the main electrical grid (이하 C) 이다. i와 j가 연결되어있고 j와 k가 연결되어있으면 i와 k는 연결되어있다고 판단한다. O끼리는 마구 연결되어있어도 상관없지만 C끼리는 연결되어있으면 안된다. 이때 주어진 그래프에 최대 몇개의 edge를 추가할 수 있는지 구하는 문제..

흠.. 여러모로 헤맸던 문제.. 틀린 솔루션가지고 안드로메다 직전까지 가고.. 나중에 정신차리고나서 간신히 해결.. 105점에 서밋.. -_-; 샘플 테스트케이스가 제대로 커버하지 못해서 많은사람이 fail 할거라고 생각했다.. 덕분에 코딩 시간에 문제 안풀고 테스트케이스 준비한게 도움이 되었다.. ㅎㅎ 챌 5개 성공 3개 실패..

우선 C가 포함되어있는 노드에 대해서 DFS로 탐색하면서 connected component를 구한다.. 이렇게 구한 각 component에 모든 가능한 edge를 추가하여 complete graph를 만든다.. 그리고 O로만 이루어진 노드들끼리는 모두 다 연결하여 complete grph를 만들고.. 이렇게 만들어진 O 덩어리를 아까 구한 C가 포함된 component 중 가장 큰놈과 붙여서.. 역시 complete graph를 만든다..

풀고나서도 그닥 확신이 안섰는데.. 결국 맞는 솔루션이었나보다.. 처음에는 MST? Union Find? 등과 관련이 있나.. 생각해보았지만.. 그냥 별다른 공식없이 마구 생각해서 푸는 문제였다..;;;; 좋은문제군.. -_-;; 코드를 보면 필요없는 부분도 있고.. 인덴트도 안맞고.. 여러모로 고심한 흔적이 있다..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 int n, m;
9 int check;
10 int grid;
11 int graph;
12
13 void dfs(int u)
14 {
15     int i;
16     for (i = 0; i < n; i++) {
17         if (check[i] == 0 && graph[u][i]) {
18             check[i] = 1;
19             dfs(i);
20         }
21     }
22 }
23
24 class AddElectricalWires {
25 public:
26
27 int maxNewWires(vector <string> wires, vector <int> gc)
28 {
29     int i, j, k, l;
30     int sum, cnt, cnt1, c_cnt;
31     int list;
32     char buf;
33     n = wires.size();
34     m = gc.size();
35     memset(grid, 0, sizeof(grid));
36     memset(graph, 0, sizeof(graph));
37     for (i = 0; i < m; i++) {
38         grid[gc[i]] = 1;
39     }
40     for (i = 0; i < n; i++) {
41         strcpy(buf, wires[i].c_str());
42         for (j = 0; j < n; j++) {
43             if (buf[j] == '0')
44                 graph[i][j] = 0;
45             else
46                 graph[i][j] = 1;
47         }
48     }
49     memset(check, 0, sizeof(check));
50     sum = 0;
51     cnt = 0;
52     cnt1 = 0;
53     for (i = 0; i < m; i++) {
54         if (check[gc[i]] == 0) {
55             check[gc[i]] = 1;
56             dfs(gc[i]);
57             cnt = 0;
58             for (j = 0; j < n; j++) {
59                 if (check[j] == 1) {
60                     check[j] = -1;
61                     list[cnt++] = j;
62                 }
63             }
64             for (k = 0; k < cnt; k++) {
65                 for (l = k+1; l < cnt; l++) {
66                     if (graph[list[k]][list[l]] == 0)
67                         sum++;
68                 }
69             }
70             if (cnt > cnt1)
71                 cnt1 = cnt;
72         }
73     }
74     cnt = 0;
75     c_cnt = 0;
76     for (i = 0; i < n; i++) {
77         if (check[i] == 0) {
78             c_cnt++;
79             check[i] = 1;
80             dfs(i);
81         }
82     }
83             for (j = 0; j < n; j++) {
84                 if (check[j] == 1) {
85                     check[j] = -1;
86                     list[cnt++] = j;
87                 }
88             }
89             for (k = 0; k < cnt; k++) {
90                 for (l = k+1; l < cnt; l++) {
91                     if (graph[list[k]][list[l]] == 0)
92                         sum++;
93                 }
94             }
95 printf("return %d\n", sum+cnt*cnt1);
96     return sum+cnt*cnt1;
97 }
98
99 };

Level2 - ContiguousCache

n 바이트 크기의 메모리가 있고 k 바이트 크기의 케쉬가 있다. n과 k와 앞으로 읽을 메모리 번지수가 나올때 최적으로 케쉬에 메모리를 읽어온다면 최소 몇번을 읽어와야 하는지 구하는 문제..
예)
n = 100, k = 3, 읽어올 주소 = {0, 2, 16, 13}
처음 0, 1, 2 를 읽고, 그다음 14, 15, 16을 읽고 마지막으로 13 만 읽으면 된다. (14, 15는 이미 남아있으므로)

to be updated..

Level3 - WifiPlanet

to be updated..

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

 TopCoder SRM 417 Div 2  (0) 2008.09.13 2008.09.07 2008.08.17 2008.08.08 2008.08.01 2008.07.20 2008.07.11 2008.07.03 2008.06.28 2008.06.15 2008.06.06