TCO08 탈락이후 오랜만에 참여한 SRM 역시.. 아침 11시 매치는 항상 나를 배신한다.. ㅠ_ㅠ;;
덕분에 올 초에 1군 복귀이후 7번째 매치만에 다시 2군으로 강등됐다.. 흑흑.. ㅠ_ㅠ
문제는 비교적 무난했는데.. 역시.. DP에서 말렸다.. 젠장!!!!

방 16등 (연속 두번 최하위.. ㅠ_ㅠ) 전체 398등..


사용자 삽입 이미지



[250] IsomorphicWords
하나의 letter가 자신또는 다른 letter로의 1대1 대응이 될 때 이를 이용하여 변환된 단어를 isomorphic이라고 한다.. 주어진 words에서 isomorphic한 단어 쌍의 개수를 구하는 문제..

단순히 임의의 모든 쌍의 단어에 대해서 isomorphic이 가능한지 체크하였다..

참고로 a->b 로 mapping될 경우.. b->a 로 mapping 되야할 필요는 없다.. 이걸 착각하는바람에.. 한참 시간을 까먹었다..

이 문제는 문제가 매우 클리어하여 div1에서는 틀린 사람이 10명도 안되었다.. 나같은경우 코딩하다 삽질하면서 한참 늦게 풀었고.. 덕분에 rating이 곤두박칠쳤다.. ㅠ_ㅠ;; 젠장.. 1문제 풀고도 최하위라니..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int test1(char* str1, char* str2)
  9 {
 10     int i;
 11     int len1, len2;
 12     char m[200], m2[200];
 13     len1 = strlen(str1);
 14     len2 = strlen(str2);
 15     if (len1 != len2)
 16         return 0;
 17     memset(m, 0, sizeof(m));
 18     memset(m2, 0, sizeof(m2));
 19     for (i = 0; i < len1; i++) {
 20         if (m[str1[i]] == 0 && m2[str2[i]] == 0) {
 21             m[str1[i]] = str2[i];
 22             m2[str2[i]] = str1[i];
 23         }
 24         else {
 25             if (m[str1[i]] != str2[i])
 26                 return 0;
 27             if (m2[str2[i]] != str1[i])
 28                 return 0;
 29         }
 30     }
 31     return 1;
 32 }
 33
 34 class IsomorphicWords {
 35 public:
 36
 37 int countPairs(vector <string> words)
 38 {
 39     int n;
 40     int i, j;
 41     int cnt;
 42     char list[100][100];
 43     n = words.size();
 44     for (i = 0; i < n; i++) {
 45         strcpy(list[i], words[i].c_str());
 46     }
 47     cnt = 0;
 48     for (i = 0; i < n; i++) {
 49         for (j = i+1; j < n; j++) {
 50             if (test1(list[i], list[j])) {
 51 printf("%s and %s\n", list[i], list[j]);
 52                 cnt++;
 53             }
 54         }
 55     }
 56 printf("cnt = %d\n", cnt);
 57     return cnt;
 58 }




[500] KeysInBoxes
n개의 box가 있고 m개의 폭탄이 있다.. 각 box안에는 다른 혹은 자신의 박스를 열수있는 열쇠가 들어있다.. box는 폭탄으로 열수도 있고 해당하는 key로 열수도 있다.. 모든 박스를 열수 있는 확률 구하기..

음.. 이 문제는 1부터 n까지의 수의 임의의 permutation 중에서 M개의 cycle이하로 생기는 경우의 수를 구하면 된다.. 이 경우 Stirling number of the first kind 가 된다고 한다.. 물론 stirling number라는 것을 알고 푼사람도 있지만.. 많은 사람이 모른 상태에서 dp로 구한 사람들이 많았다..

아래는 srirling number를 구현한 코드이다..
dp[i][j] = i개의 수가 j개의 cycle을 만들는 경우의 수..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 long long gcd(long long a, long long b)
  9 {
 10     if (b == 0)
 11         return a;
 12     return gcd(b, a % b);
 13 }
 14
 15 class KeysInBoxes {
 16 public:
 17
 18 string getAllKeys(int N, int M)
 19 {
 20     int i, j;
 21     char buf[100];
 22     long long dp[30][30];
 23     long long non, den, g;
 24     string res;
 25
 26     memset(dp, 0, sizeof(dp));
 27     dp[1][1] = 1;
 28     for (i = 2; i <= N; i++) {
 29         for (j = 1; j <= i; j++) {
 30             dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * (i-1);
 31         }
 32     }
 33     den = 1;
 34     for (i = 1; i <= N; i++) {
 35         den *= i;
 36     }
 37     non = 0;
 38     for (i = 1; i <= M; i++) {
 39         non += dp[N][i];
 40     }
 41     g = gcd(non, den);
 42     non /= g;
 43     den /= g;
 44     sprintf(buf, "%lld/%lld", non, den);
 45     res = buf;
 46     return res;
 47 }
 48
 49 };




[1000] Transformation


to updated..

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

TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
SRM 395 Div1  (0) 2008.04.09
TopCoder SRM 394 Div 1  (2) 2008.03.24
흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27
TopCoder TCO08 Online Round 1  (2) 2008.02.17
TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25

Leave a Comment


to Top