어제 밤 12시에 열린 매치.. 엄청나게 많은 사람들이 참가했다.. 총 1706명.. 한국사람은 무려 56명이 참가했다.. 아마 역대 최다가 아닌가 생각된다.. 본격적으로 ACM 시즌 시작인가? ㅎㅎ 덕분에 무지 흥미진진한 매치였다.. 이번에는 평소보다 문제가 쉬웠는데 또 한문제밖에 풀지 못했다.. 아.. 아쉽.. 600점짜리 문제를 다 잘 풀어놓고.. 막판에 결정적인 실수를 하나 하고 말았다.. 요즘 열대야 때문에 다들 밤에 잠을 못이루겠지만.. 나는 이문제 틀려서 억울해서 잠을 못이뤘다.. 젠장.. rating은 6점 상승.. -_- 어쨋든 좋은 경험이었다.. 다음엔 꼭 level2를 풀어주리라..

사용자 삽입 이미지
어마어마한 참가자들.. SRM에서 1700명 넘게 참가한적도 처음보는거같고.. 그중에 한국인이 무려 56명이나 참가했다.. 와.. 탑코더가 점점 유명해지는구나..~

사용자 삽입 이미지



Level1 - OrderedSuperString
input으로 여러개의 string이 들어온다.. 이 string을 순서대로 붙여서 만들 수 있는 가장 짧은 string을 구하기.. string을 붙일 때 중첩이 가능하다.. 그러나 이전에 앞에서 붙였던 string의 index보다 더 앞에 붙일수는 없다.. 예를들어 {"abc", "bcd", "de", "f"} => "abcdef" 가 되지만, {"abcd", "de", "bcd"} => "abcdebcd" 가 된다..

코딩은 그냥 greedy하게 앞에서부터 붙였다.. 이때 바로 앞에서 붙였을때의 index와 현재까지 만들어진 string의 길이를 기억해두면 편하다..

음.. 쉬운문제인데 좀 오래걸렸다.. 문제를 이해하는데 좀 오래걸리고.. 코딩하는데도 좀 오래걸렸나..?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class OrderedSuperString {
  9 public:
 10
 11 int getLength(vector <string> words)
 12 {
 13     int n, i, j, k, len2;
 14     int idx[100], len[100];
 15     char w[100][100];
 16     char str[10000];
 17     n = words.size();
 18     for (i = 0; i < n; i++) {
 19         strcpy(w[i], words[i].c_str());
 20         idx[i] = 0;
 21     }
 22     memset(str, 0, sizeof(str));
 23     strcpy(str, w[0]);
 24     idx[0] = 0;
 25     len[0] = strlen(w[0]);
 26     for (i = 1; i < n; i++) {
 27         len2 = strlen(w[i]);
 28         for (j = idx[i-1]; j <= len[i-1]; j++) {
 29             for (k = 0; k < len2; k++) {
 30                 if (w[i][k] != str[j+k] && j+k < len[i-1]) {
 31                     break;
 32                 }
 33             }
 34             if (k == len2) {
 35                 for (k = 0; k < len2; k++) {
 36                     str[j+k] = w[i][k];
 37                 }
 38                 if (j+k > len[i-1]) {
 39                     len[i] = j+k;
 40                     str[j+k] = 0;
 41                 }
 42                 else {
 43                     len[i] = len[i-1];
 44                 }
 45                 idx[i] = j;
 46                 break;
 47             }
 48         }
 49     }
 50 printf("str = %s\n", str);
 51     return len[n-1];
 52 }
 53
 54 };



Level2 - MagicalSpheres
문제는 진짜 magical sphere가 몇개 있고.. 가짜도 몇개 있고.. gnome이 이중에 몇번을 .. 어쩌구.. 설명하자면 복잡하고.. 간단히 nCr 을 나눌 수 있는 g보다 작은 수 중 가장 큰수 구하기 이다.. 여기서 n = s+f, r = s 가 된다..

우선 1부터 g까지 루프를 돌면서 그 수가 nCr 을 나눌 수 있는지 판단한다..
어떤수로 나눠지는지 아닌지 알려면 factoring(소인수분해)을 하고 각 factor의 개수를 비교하면 된다..
nCr의 factor를 구하기 위해서 다음과 같이 바꾼다.. nCr = n! / ((n-r)! * r!)
어떤 n! 에 소인수 k가 몇번 들어가있는지는 이미 잘 알려진 공식에 의해 쉽게 구할 수 있다..
이 내용들을 대략 조합해서 풀면 된다.. ㅎㅎ

이 문제는 정말 아쉽게 fail 했다.. 접근 방법까지 잘 찾았는데.. 결국 코드에 약간의 문제가 있었다.. 비슷한 코드가 좀 있어서 마구 copy & paste를 남발했는데.. 결국 붙여놓고 고쳐야 할 부분을 깜빡하고 말았다.. ㅠ_ㅠ 결국은 system fail..

근데 매치 끝나고 고쳐서 서밋해보니 딱 하나의 case에서 TLE가 났다.. 이건 뭥미.. prime factor들의 개수를 다 저장하고 나중에 넘치는지 모자르는지 구했는데.. 그것보다 각 prime factor에 대해서 개수를 구하고 개수가 모자르면 바로 break 하는 방법으로 고쳤다.. 그리고 나도 남들처럼 prime factor 개수 구하는부분을 함수로 만들어 보았다..;;

참고로 이문제는 UVa 10139 - Factovisors 문제와 연관이 있다.. 좋은 문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 char is_prime[100001];
  9 int prime[10000];
 10 int prime_cnt;
 11
 12 void sieve()
 13 {
 14     int i, j;
 15     prime_cnt = 0;
 16     memset(is_prime, -1, sizeof(is_prime));
 17     is_prime[0] = is_prime[1] = 0;
 18     for (i = 2; i <= 100000; i++) {
 19         if (is_prime[i]) {
 20             for (j = 2; i * j <= 100000; j++)
 21                 is_prime[i*j] = 0;
 22             prime[prime_cnt++] = i;
 23         }
 24     }
 25 }
 26
 27 int n_div(int a, int b)
 28 {
 29     int cnt;
 30     long long temp;
 31     cnt = 0;
 32     temp = b;
 33     while (temp <= a) {
 34         cnt += (a / temp);
 35         temp *= b;
 36     }
 37     return cnt;
 38 }
 39
 40 class MagicalSpheres {
 41 public:
 42
 43 int divideWork(int s, int f, int g)
 44 {
 45     int i, cnt, n;
 46     long long temp;
 47     sieve();
 48     for (n = g; n > 1; n--) {
 49         temp = n;
 50         for (i = 0; i < prime_cnt && prime[i] <= n; i++) {
 51             if (temp % prime[i] == 0) {
 52                 cnt = 0;
 53                 while (temp % prime[i] == 0) {
 54                     cnt++;
 55                     temp /= prime[i];
 56                 }
 57                 if (n_div(s+f, prime[i]) - n_div(s, prime[i]) - n_div(f, prime[i]) - cnt < 0) {
 58                     goto X;
 59                 }
 60             }
 61         }
 62         return n;
 63 X: ;
 64     }
 65     return 1;
 66 }
 67
 68 };



Level3 - GridColoring
row by col 의 grid가 주어지고.. grid안의 두점을 random하게 선택해서 그 점으로 만들어지는 사격형을 모두 칠한다.. 이러한짓을 k번 반복할때.. 결국 한번도 안칠해지는 사각형 개수의 기대값 구하기..

에디토리얼을 참조해서 풀었다..
일단 임의의 cell (x, y)가 칠해질 확률을 구하면
col에 대해서 선택하는 두 점의 x좌표가 왼쪽 점은 x보다 작거나 같아야하고 오른쪽 점은 x보다 크거나 같아야 한다.. 따라서 경우의 수는 (x+1)*(col-x)가 된다.. 그러나 오른쪽을 선택하고 왼쪽을 선택하는 경우와 왼쪽을 선택하고 오른쪽을 선택하는 경우 두가지가 다르므로 * 2 를 해야한다.. 그러나 선택한 두 점이 같은경우가 있으므로 - 1 을 해야한다.. 따라서..

col에 대해서 x가 선택될 확률 px =  (2 * (x+1)*(col-x) -1 ) / (col*col)
row에 대해서 y가 선택될 확률 py = (2 * (y+1)*(row-y) - 1) / (row*row)

cell (x, y) 가 칠해질 확률 p(x, y) = px * py

이 짓을 k번 하는데.. k번을 했는데도 (x, y)가 안칠해지 확률 q = (1 - p(x, y))^k
결국 각 cell이 칠해질 확률은 한번도 안칠해지지만 않으면 되므로 1 - q가 된다..
따라서 모든 cell에 대해서 구한 1 - q를 다 더해주면 된다..

아.. 확률은 어렵구만..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8
  9 double get_p(double x, double y, double rows, double cols)
 10 {
 11     double px, py;
 12     px = 2 * (x+1) * (rows-x) - 1;
 13     py = 2 * (y+1) * (cols-y) - 1;
 14     return px * py / (rows * rows * cols * cols);
 15 }
 16
 17 class GridColoring {
 18 public:
 19
 20 double area(int K, int rows, int cols)
 21 {
 22     int i, j;
 23     double sum, temp;
 24     sum = 0;
 25     for (i = 0; i < rows; i++) {
 26         for (j = 0; j < cols; j++) {
 27             temp = get_p(i, j, rows, cols);
 28             sum += 1.0 - pow(1.0-temp, (double)K);
 29         }
 30     }
 31     return sum;
 32 }
 33
 34 };


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

TopCoder SRM 416 Div2  (0) 2008.09.07
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 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

to Top