TopCoder SRM 442 Div 1

Problem Solving/TopCoder logs 2009. 6. 14. 12:50

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

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




[250] 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[100010];
 12 char is_prime[1000001];
 13 int prime[100000];
 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[0] = is_prime[1] = 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 };




[550] BedroomFloor




to be updated..



[950] 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[200][200];
 68     int ag[200][200];
 69     int i, j, a, l;
 70     int res;
 71     char buf[200];
 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[0][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
Beta SRM (Member-Run Round)  (0) 2009.08.19
[SRM 446] 매치가 뭐 이래..?! (Unchallengeable Match)  (6) 2009.08.09
TopCoder SRM 445 Div 1  (0) 2009.07.24
[SRM 444] 개인 역대 최고 등급 경신..~  (0) 2009.07.09
[SRM 441] 탑코더 아레나.. 중국 뉴비들에게 DDOS공격 받고 사망..  (0) 2009.05.28
TopCoder SRM 440 Div 1 - 드디어 Yellow 등극..  (0) 2009.05.14
말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Round 1  (0) 2009.03.08
  • By helloneo

to Top

티스토리툴바