새벽 1시에 있었던 매치.. 이번에는 IPSC2008과 SRM402가 시간이 겹치면서 매우 흥미로은 매치가 되었다.. 나같은 경우  탑코더보다 4시간 앞서 시작된 IPSC와 사투를 벌이다가 중간에 탑코더로 갈아탔다.. IPSC가 저녁 9시부터 시작되었고(나는 10시부터 참여) 탑코더가 2시 반까지 진행되었으니.. 4시간 반동안 컨테스트를 치룬 셈이다.. 휴.. 이제는 체력이 떨어져서 두탕뛰는것도 못하겠네.. 한국사람들 중에는 나처럼 갈아탄 경우도 있고.. 끝까지 IPSC만 물고 늘어진 사람도 있고.. 탑코더만 참여한 사람도 있었다..

SRM402는 음.. 250점 문제부터 젠장할 확률 문제가 나오면서.. -_- 다들 줄줄이 떨어졌다..;; 겨우 한문제 해결.. rating은 소폭 상승.. 이제 1300에 거의 다가섰다.. 언제 yellow로 올라가보나..; 이거 뭐 챌은 성공해본 적이 없는것 같군..

방 8등 전체 318등..


사용자 삽입 이미지



[250] RandomSort
input으로 1~n 까지의 수의 permutatatin이 들어온다. 이 배열을 오름차순으로 sort하려고 할때.. sort하는 규칙은 i < j && permutation[i] > permutation[j] 인 임의의 (i, j)를 뽑아서 swap 한다. 여기서 임의의(i, j)가 뽑힐 확률은 모두 균등하다. 이 배열이 sort가 되기 위해 필요한 swap의 개수의 기대값 구하기..

처음에 확률 문제라 매우 당황했지만.. 250이 어려울리 없다고 마인드 컨트롤 한 후 brute force 비슷하게 접근했다.. 적당한 수식을 생각한 후 recursion + memorization으로 해결..

우선 주어진 배열에 대해서 swap을 적용할 수 있는 모든 (i, j) 쌍에 대해서 하나씩 swap 하면서 다음 단계로 넘어간다.. 중복된 상태를 계산하지 않기 위해 memorization 기법을 이용했다..

처음 코딩 후 답이 안나와서.. 접근이 틀렸나..? 생각하고 포기하고 다른문제를 보는 바람에 시간을 많이 까먹었다.. 흠.. 알고보니 기초적인 실수를.. -_-;;

그리고.. STL map에서 key로 vector<int> 가 가능하다는걸 저번에 배웠기때문에.. -_-;; 이번에 한번 써먹어 보았다.. 오.. 편하군..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 using namespace std;
  8
  9 map<vector<int> , double> mm;
 10
 11 int is_sorted(vector<int> v)
 12 {
 13     int i;
 14     for (i = 1; i < v.size(); i++) {
 15         if (v[i-1] > v[i])
 16             return 0;
 17     }
 18     return 1;
 19 }
 20
 21 double dfs(vector<int> v)
 22 {
 23     int i, j, k;
 24     int a, size;
 25     double res;
 26 /*
 27 for (i = 0; i < v.size(); i++) {
 28 printf(" %d", v[i]);
 29 }
 30 printf("\n");
 31 */
 32     if (is_sorted(v)) {
 33         return 0;
 34     }
 35     if (mm.find(v) != mm.end()) {
 36         return mm[v];
 37     }
 38     size = v.size();
 39     a = 0;
 40     for (i = 0; i < size; i++) {
 41         for (j = i+1; j < size; j++) {
 42             if (v[i] > v[j]) {
 43                 a++;
 44             }
 45         }
 46     }
 47     res = 0.0;
 48     for (i = 0; i < size; i++) {
 49         for (j = i+1; j < size; j++) {
 50             if (v[i] > v[j]) {
 51                 vector<int> v2;
 52                 for (k = 0; k < size; k++) {
 53                     v2.push_back(v[k]);
 54                 }
 55                 v2[i] = v[j];
 56                 v2[j] = v[i];
 57                 res += (dfs(v2)+1.0) / (a*1.0);
 58             }
 59         }
 60     }
 61     mm[v] = res;
 62     return res;
 63 }
 64
 65 class RandomSort {
 66 public:
 67
 68 double getExpected(vector <int> permutation)
 69 {
 70     double res;
 71 printf("...\n");
 72     res = dfs(permutation);
 73 printf("res = %lf\n", res);
 74     return res;
 75 }
 76
 77 };




[450] LargestGap
XXX 로 연속된 것을 block이라고 하고 ... 으로 연속된 것을 gap이라고 한다. 주어진 string을 순서대로 한줄로 붙여서 나오는 string 중 block 하나를 제거할 수 있다. 이때 가장 큰 gap이 생기게 하려면 어떤 block을 삭제하여야 하는지 구하는 문제.. string은 circular 형태라서 맨 끝이 gap은 맨 앞의 gap과 연결된다.. (block도 연결되나?) 가장 큰 gap이 같을 경우, 두번째 큰 gap이 큰 경우 구하기.. gap이 모두다 같은경우 가장 앞에 있는 block 제거..

이 문제는 문제를 이해하는데 거의 모든 시간을 보냈다.. -_- 그냥 시키는데로 하면 되는 문제인듯 한데.. 코딩은 약간 번거롭다.. 또한 tie breaker 조건이 까다로워서 그다지 쉽지는 않은 문제.. 우리 방에 있는 사람들도 모두 fail했다..(나이스!!)

to be updated..




[1000] IncreasingSequence



to be updated..

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

TopCoder SRM 409 Div 1 (완료)  (0) 2008.07.11
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 401 Div1  (2) 2008.05.07
TopCoder SRM 400 Div 1  (0) 2008.05.02
리눅스에서 탑코더하기..  (0) 2008.05.01
TopCoder SRM 399 Div 1  (0) 2008.04.25
TopCoder SRM 398 Div1  (0) 2008.04.16

to Top