TopCoder SRM 391 Div1

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

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

[250] IsomorphicWords

Problem Statement
     
Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter. The ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.
For example, the words "abca" and "zbxz" are isomorphic because we can map 'a' to 'z', 'b' to 'b' and 'c' to 'x'.
Given a vector <string> words, return how many (unordered) pairs of words are isomorphic.
Definition
   
Class:
IsomorphicWords
Method:
countPairs
Parameters:
vector <string>
Returns:
int
Method signature:
int countPairs(vector <string> words)
(be sure your method is public)
   
 
Constraints
-
words will contain between 2 and 50 elements, inclusive.
-
Each element of words will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
-
All elements of words will have the same length.
-
There will be no duplicates in words.
Examples
0)
 
   
{"abca", "zbxz", "opqr"}
Returns: 1
"abca" and "zbxz" are isomorphic, but none of the two is isomorphic with "opqr".
1)
 
   
{"aa", "ab", "bb", "cc", "cd"}
Returns: 4
The four isomorphic pairs are {"aa", "bb"}, {"aa", "cc"}, {"bb", "cc"} and {"ab", "cd"}.
2)
 
   
{ "cacccdaabc", "cdcccaddbc", "dcdddbccad", "bdbbbaddcb",
  "bdbcadbbdc", "abaadcbbda", "babcdabbac", "cacdbaccad",
  "dcddabccad", "cacccbaadb", "bbcdcbcbdd", "bcbadcbbca" }
Returns: 13
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

하나의 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

Problem Statement
     
There are N boxes numbered from 1 to N and N keys numbered from 1 to N. The i-th key can only be used to open the i-th box. Now, we randomly put exactly one key into each of the boxes. We assume that all configurations of keys in boxes occur with the same probability. Then we lock all the boxes. You have M bombs, each of which can be used to open one locked box. Once you open a locked box, you can get the key in it and perhaps open another locked box with that key. Your strategy is to select a box, open it with a bomb, take the key and open all the boxes you can and then repeat with another bomb.
Return the probability that you can get all the keys. The return value must be a string formatted as "A/B" (quotes for clarity), representing the probability as a fraction. A and B must both be positive integers with no leading zeroes, and the greatest common divisor of A and B must be 1.
Definition
   
Class:
KeysInBoxes
Method:
getAllKeys
Parameters:
int, int
Returns:
string
Method signature:
string getAllKeys(int N, int M)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 20, inclusive.
-
M will be between 1 and N, inclusive.
Examples
0)
 
   
2
1
Returns: "1/2"
When box 1 contains key 2, you can get all the keys.
1)
 
   
2
2
Returns: "1/1"
When N=M, you can always get all the keys.
2)
 
   
3
1
Returns: "1/3"
There are 6 possible configurations of keys in boxes. Using 1 bomb, you can open all the boxes in 2 of them:
box 1 - key 2, box 2 - key 3, box 3 - key 1;
box 1 - key 3, box 2 - key 1, box 3 - key 2.
3)
 
   
3
2
Returns: "5/6"
Now, when you have 2 bombs, you are only unable to get all the keys in the following configuration: box 1 - key 1, box 2 - key 2, box 3 - key 3.
4)
 
   
4
2
Returns: "17/24"
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

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

Problem Statement
     
You are to transform a positive integer vector (A1,A2,...,An) into another positive integer vector (B1,B2,...,Bn) of the same length. The transformation must satisfy the conditions below: 1) For 1 < = i < =n., Bi must evenly divide into Ai. 2) The least common multiple of all Ai should be equal to that of all Bi.
You are given the original integer vector as a vector <string> A, where the i-th (1-based) element is a positive integer representing Ai. Return a vector <string> containing the transformed integer vector in the same format. Each element of the return vector <string> must be a positive integer with no leading zeroes. If there are multiple solutions, return the one where the first number is the smallest. If there are still multiple solutions, return the one with the smallest second number etc.
Definition
   
Class:
Transformation
Method:
transform
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> transform(vector <string> A)
(be sure your method is public)
   
 
Notes
-
The least common multiple of a group of positive integers is the least positive integer which is a multiple of every integer in the group.
Constraints
-
A will contain between 1 and 50 elements, inclusive.
-
Each element of A will contain digits ('0' - '9') only.
-
Each element of A will represent a positive integer without leading zeros.
-
Each element of A will contain between 1 and 18 characters, inclusive.
Examples
0)
 
   
{"1","2"}
Returns: {"1", "2" }
 
1)
 
   
{"2","3","6"}
Returns: {"1", "1", "6" }
{1,1,6},{1,3,2},{1,3,6},{2,1,3},{2,1,6},{2,3,1},{2,3,2},{2,3,3},{2,3,6} are all transformation results.
2)
 
   
{"210","2","3","5","7"}
Returns: {"1", "2", "3", "5", "7" }
 
3)
 
   
{"6","2","3","4","9"}
Returns: {"1", "1", "1", "4", "9" }
 
4)
 
   
{"6","2","3","4","9","8"}
Returns: {"1", "1", "1", "1", "9", "8" }
 
5)
 
   
{"3637","260","26122993443584","47715564111559878","2","871126696052836","3492829317","83024857214176826"}
Returns:
{"3637",
 "5",
 "26122993443584",
 "7952594018593313",
 "1",
 "217781674013209",
 "3492829317",
 "41512428607088413" }
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

to updated..