드디어 TopCoder Open 09 가 시작되었다..~
방금전에 끝난 Qualification Round 1에서 삽질한 끝에.. 830등으로 마감..
결국 온라인 1라운드 진출 실패.. 주말에 있을 Qual2를 다시 도전하게 되었다.. ㅠ_ㅠ

탑코더도 미쿡의 경기한파의 영향을 받아서.. onsite 진출자 정원을 18명으로 팍 줄였다.. ㅠ_ㅠ
그래서 퀄 라운드부터 경쟁이 열라 치열해졌는데.. 퀄 라운드 3번중에 한번은 적어도 550등 안에 들어야한다..
흠.. 그래도 작년에는 온라인 1라운드까지는 진출했는데.. 다음 새벽매치에 사활을 걸어야겠다.. ㅠ_ㅠ

500점짜리를 pass했으면 여유있게 통과했을텐데.. 흠..
segmented sieve를 대략 응용해서 잘 풀었는데.. 왜 챌당했을까..?

앞으로의 일정은..


내 작년 기록을 보니.. 252등으로 퀄라운드 여유있게 통과했네.. 흐미..;;
1년사이에 무지 빡세졌네..;;




Level1 - SortingWithPermutation
size n의 배열 a가 주어지고.. 임의의 permutation P 를 이용하여 배열 a를 b로 변환할때 b가 sort되도록 하고싶다.. 이러한 permutation P 구하기.. 답이 여러개이면 lexy smallest로..
단, 변환 규칙은 b[p[i]] = a[i]  

쉬운 문제인데 매우 삽질했다.. b[i] = a[p[i]] 이라면 좀더 직관적이었을텐데.. index와 value를 마구 헷갈리면서 시간을 매우 많이 낭비했다.. ㅠ_ㅠ

나같은 경우 index와 value를 pairing해서 sort했다.. 근데 답을 출력해보니 index와 value가 바껴서 나와서 다시한번 sort했다.. -_-;;

흠.. 그리고 C++에 make_pair() 란게 있는거같은데.. 요거 어떻게쓰는거지..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 typedef struct _d {
  9     int num, no;
 10 } DATA;
 11
 12 int comp(const void* x, const void* y)
 13 {
 14     DATA* a = (DATA*)x;
 15     DATA* b = (DATA*)y;
 16     if (a->num != b->num)
 17         return a->num - b->num;
 18     return a->no - b->no;
 19 }
 20
 21 class SortingWithPermutation {
 22 public:
 23
 24 vector <int> getPermutation(vector <int> a)
 25 {
 26     vector<int> res;
 27     DATA data[100];
 28     DATA data2[100];
 29     int n;
 30     int i;
 31     n = a.size();
 32     for (i = 0; i < n; i++) {
 33         data[i].no = i;
 34         data[i].num = a[i];
 35     }
 36     qsort(data, n, sizeof(DATA), comp);
 37     for (i = 0; i < n; i++) {
 38         //printf("p[%d] = %d\n", i, data[i].no);
 39         data2[i].no = i;
 40         data2[i].num = data[i].no;
 41     }
 42     qsort(data2, n, sizeof(DATA), comp);
 43     for (i = 0; i < n; i++) {
 44         res.push_back(data2[i].no);
 45     }
 46     return res;
 47 }
 48
 49 };



Level2 - SquareFreeNumbers
n^2 꼴의 수로 나눠지지 않는 수를 square-free 라고 한다.. min부터 max 사이에 square-free 수가 몇개인지 구하기..

이 문제는 segmented sieve의 응용으로 풀 수 있다..
쉬운문제인데 매치때 뭔가 코딩이 잘못되었는지 WA를 받았다.. ㅠ_ㅠ;

일단 sieve 배열을 max-min+1 개만 채우고 sieve[i] := sieve[i-min] 의 정보를 저장하는 식이다..
이 문제의 핵심은 어떤 제곱수 k 가 sieve의 몇번째 index부터 나누어 떨어지는지를 어떻게 빨리 찾아내느냐이다..~
코드 참조.. ㅎㅎ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 char is_prime[1100000];
  9
 10 class SquareFreeNumbers {
 11 public:
 12
 13 int getCount(long long l, long long u)
 14 {
 15     int res;
 16     long long i, j, start, temp;
 17     memset(is_prime, -1, sizeof(is_prime));
 18     for (i = 2; i * i <= u; i++) {
 19         temp = i * i;
 20         start = (l / temp) * temp;
 21         while (start < l) {
 22             start += temp;
 23         }
 24         for (j = start; j <= u; j += temp) {
 25             is_prime[(int)(j-l)] = 0;
 26         }
 27     }
 28     res = 0;
 29     for (i = 0; i <= u-l; i++) {
 30         if (is_prime[i]) {
 31 //cout << i+l << " is prime.." << endl;
 32             res++;
 33         }
 34     }
 35     return res;
 36 }
 37
 38 };



Level3 - PrimePairs



to be updated..

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

말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Round 1  (0) 2009.03.08
TCO09 Qual 3 (완료)  (0) 2009.03.05
TCO09 Qual 2  (0) 2009.03.01
TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07
TopCoder SRM 428 Div 1  (0) 2008.12.03
탑코더 스름 426 디비젼 1  (0) 2008.11.25
TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13

to Top