## TopCoder SRM 442 Div 1

어제 새벽 1시에 열린 매치..~
이번에도 중국애들이 너무 많이 참여해서.. 1850 limit이 다 차버렸다..~
덕분에 채팅방에서는 limit 좀 늘려달라고 원성이 자자했다..~
나는 저번에 한번 당했기때문에 이번에는 3시간 전에 미리 등록..;;

이번 매치에서는 250을 비교적 빨리 풀어서 다시 yellow로 복귀했다..~
250을 풀고나서 550을 열었는데.. 코딩이 좀 난해해서 정확히 코딩할 자신이 없었다..
그래서 남은시간엔 그냥 놀았다.. -_-;;
흠.. 앞으로 550-950 set 이 나오면 950부터 열어야겠다..~  Underprimes

어떤 수 X를 factorization했을때, prime factor의 개수가 prime이면 underprime이라고 한다.. 예를들어 12 = 2*2*3 이므로, prime factor의 개수는 3이고 3은 prime이므로 12는 underprime이다..
A~B 사이에 underprime이 몇개있는지 구하기..

그냥 문제에서 시키는대로 factoring하고 prime 체크하면 된다..
나는 이전에 짜둔 코드가 있어서 그냥 복.붙 했다.. -_- 사실 sieve는 한번만 써도 되는데..
생각하기 귀찮아서.. 그냥 뒀다.. ㅋㅋ 비슷한 코드가 두벌 있으니 좀 이상하네..;;

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 //#define INF 999999999
10
11 int n_fact;
12 char is_prime;
13 int prime;
14 int prime_cnt;
15
16 void fact_sieve()
17 {
18     int i, j;
19     memset(n_fact, 0, sizeof(n_fact));
20     for (i = 2; i <= 100000; i++) {
21         if (n_fact[i] == 0) {
22             n_fact[i] = 1;
23             for (j = 2; i*j <= 100000; j++) {
24                 n_fact[i*j] = n_fact[i] + n_fact[j];
25             }
26         }
27     }
28 }
29
30 void sieve()
31 {
32     int i, j;
33     memset(is_prime, -1, sizeof(is_prime));
34     prime_cnt = 0;
35     is_prime = is_prime = 0;
36     for (i = 2; i <= 100000; i++) {
37         if (is_prime[i]) {
38             for (j = 2; i * j <= 100000; j++) {
39                 is_prime[i*j] = 0;
40             }
41             prime[prime_cnt++] = i;
42         }
43     }
44 }
45
46 class Underprimes {
47 public:
48
49 int howMany(int A, int B)
50 {
51     int i, res;
52     sieve();
53     fact_sieve();
54     res = 0;
55     for (i = A; i <= B; i++) {
56         if (is_prime[n_fact[i]])
57             res++;
58     }
59     return res;
60 }
61
62 };

 BedroomFloor

to be updated..

 NowhereLand

각 city에 guard를 배치하려고 한다.. guard를 제공하는 company가 k 개 있고.. 각 company가 지원할 수 있는 city는 정해져있다.. 또한 이미 몇 city에는 임의의 company의 guard가 배치되어있다.. 각 city마다 협력하는 city가 있는데.. city i 와 j 가 협력관계라면 i에 a 회사의 guard가 배치되어있다면 j에도 a 회사의 guard가 배치되어야 한다.. 그렇지 않으면 conflct 라고 한다.. 임의의 guard를 더 추가한다고 할 때 발생하는 conflct 를 최소하하기..

문제 이해하는게 드럽게 어렵지만.. 일단 이해하고 나면 쉬운문제이다..

하나의 city에는 하나의 company의 guard만 배치될 필요는 없다.. 즉, 여러명을 한곳에 배치해도 된다는말..
그래서 각 company 끼리는 서로 무관하므로 독립적으로 생각해서 풀면 된다..

이미 guard가 배치된곳을 source쪽으로 연결하고 guard를 배치할 수 없는곳을 sink에 연결하여
min cut을 구하면 된다..

이것도 minimum vertex cover = min cut 이런 개념인것인가..??

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <queue>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 //#define max(x, y) ((x) > (y) ? (x) : (y))
10 #define INF 999999999
11 #define MAXN 201
12
13 int graph[MAXN][MAXN];
14 int n, m;
15
16 int get_augment_path(int s, int t)
17 {
18     int i, j, c;
19     int min1;
20     int path[MAXN];
21     queue<int> q;
22     q.push(s);
23     memset(path, -1, sizeof(path));
24     while (!q.empty() && path[t] == -1) {
25         c = q.front();
26         /* for (i = 0; i < n; i++) {   <--- if 0-based index */
27         for (i = 0; i <= n; i++) {
28             if (path[i] == -1 && graph[c][i] > 0) {
29                 path[i] = c;
30                 q.push(i);
31             }
32         }
33         q.pop();
34     }
35     if (path[t] == -1)
36         return 0;
37     min1 = INF;
38     j = t;
39     for (i = path[j]; j != s; i = path[j = i]) {
40         if (min1 > graph[i][j])
41             min1 = graph[i][j];
42     }
43     j = t;
44     for (i = path[j]; j != s; i = path[j = i]) {
45         graph[i][j] -= min1;
46         graph[j][i] += min1;
47     }
48     return min1;
49 }
50
51 int ford_fulkerson(int s, int t)
52 {
53     int c, flow;
54     flow = 0;
55     while ((c = get_augment_path(s, t)) > 0) {
56         flow += c;
57     }
58     return flow;
59 }
60
61 class NowhereLand {
62 public:
63
64 int placeGuards(vector <string> cities, int k, vector <string> guards, vector <string> agencies)
65 {
66     int size;
67     int gd;
68     int ag;
69     int i, j, a, l;
70     int res;
71     char buf;
72     char* ptr;
73
74     size = cities.size();
75     memset(gd, 0, sizeof(gd));
76     memset(ag, 0, sizeof(ag));
77     for (i = 0; i < size; i++) {
78         strcpy(buf, guards[i].c_str());
79         ptr = strtok(buf, " ");
80         while (ptr != NULL) {
81             sscanf(ptr, "%d", &a);
82             gd[i][a] = 1;
83             ptr = strtok(NULL, " ");
84         }
85     }
86     for (i = 0; i < size; i++) {
87         strcpy(buf, agencies[i].c_str());
88         ptr = strtok(buf, " ");
89         while (ptr != NULL) {
90             sscanf(ptr, "%d", &a);
91             ag[i][a] = 1;
92             ptr = strtok(NULL, " ");
93         }
94     }
95
96     res = 0;
97     n = size+1;
98     for (i = 0; i < k; i++) {
99         memset(graph, 0, sizeof(graph));
100         for (j = 0; j < size; j++) {
101             for (l = 0; l < size; l++) {
102                 if (cities[j][l] == '1') {
103                     graph[j+1][l+1] = 1;
104                 }
105             }
106         }
107         for (j = 0; j < size; j++) {
108             if (gd[j][i])
109                 graph[j+1] = INF;
110             if (!ag[j][i])
111                 graph[j+1][size+1] = INF;
112         }
113         res += ford_fulkerson(0, n);
114     }
115     return res;
116 }
117
118 };

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

 TopCoder SRM 448 Div 1  (0) 2009.09.11 2009.08.19 2009.08.09 2009.07.24 2009.07.09 2009.06.14 2009.05.28 2009.05.14 2009.04.20 2009.03.25 2009.03.08

1. Chaika 2009.06.14 15:46 신고

ㅋㅋㅋ 전 문제 읽자마자 형 블로그 달려와서 에라토스테네스 복.붙. 해갔어요 ㅋㅋㅋ

• 2009.06.14 22:59 신고

오오.. yellow에서도 잘하네..~ 이제 red도 노려봐야지..~

헉.. 나도 그렇게 할껄.. 괜히 삽질하다가 1시간이나 걸렸네... -0-

• 2009.06.14 23:06 신고

음.. 그냥 짰는데도 240점 넘는사람들이 있네요.. 다들 어떻게 한건지..;;

3. Chaika 2009.06.18 11:38 신고

헐...... 형이 짠 코드 지금 침착하게 봤는데,

전 그냥 sieve로 했는데, 형 코드에는 factorization sieve가 있네요.

뭔가하고 따라가봤는데 진짜 멋진 코드인듯 ㅠㅠ

(형 말마따나 그냥 sieve는 필요없고 위의 fact_sieve만 있으면 되겠는데요 ㅎㅎ)

• 2009.06.18 13:20 신고

어.. n_fact[i] == 1 인 i 가 곧 prime이니깐.. 다른사람코드를 보니.. sieve를 변형해서 푼 사람 꽤 있던데..~

4. Chaika 2009.06.23 15:12 신고

트랙백 해갔어요~ ㅋㅋ

근데 한번 수정했는데 이상하게되었네요;;;

트랙백이 2개가 남아버렸네;;;;

• 2009.06.23 20:59 신고

티스토리 버그인가보네.. ㅋㅋㅋ

5. 안녕하세요 2016.08.26 22:41

안녕하세요? nowhereland 소스코드 잘 읽었습니다. 제가 여쭤보고 싶은게 있는데요. 각 도시에서 경비를 고용한 도시는 어디이고 고용을 안한 도시는 어디인지를 출력하는 방법을 알고싶은데요. 혹시 그 방법을 알고계신가요?

• 2016.08.28 22:23 신고

너무 오래된 포스팅이라 무슨 문제인지도 모르겠지만,,
ford fulkerson 으로 구했다면 residual network 상태를 보면 되지 않을까요?
a -> b 로 1 만큼 보냈다면 graph[a][b] 가 1만큼 감소해있을 것 같네요..

• 안녕하세요 2016.08.30 07:35

댓글 감사합니다.

http://stackoverflow.com/questions/21471043/find-all-edges-in-min-cut

사실 여기서 도움 얻었습니다. 수고하세용