음.. 이번 match는 완전.. -_-;;
누구의 말따라.. bloodthristy match였다.. 매우 tricky한 문제들로인해.. challenge가 난무했다..
역배점이라서 1000점이 젤 쉬운문제라는 말도 있었는데.. 결과를 보니.. 꼭 그렇지도 않았다.. 완전..;;
뭐랄까.. 완전 낚인느낌.. challenge time에서 살아남은 사람들도.. 결국 system judge에서 다 fail했다.. ㅠ_ㅠ

1000점짜리 문제를 보니 topological sort 비스무리해서.. 한번 시도해봤는데.. 결국 system fail..;; 문제가 tricky하다는 것은 알고있었는데.. 나도 fail이었을줄은 몰랐다.. ㅠ_ㅠ

사용자 삽입 이미지
이 처참한 현장이 보이는가..!

사용자 삽입 이미지
더더욱 놀라운것은.. 나는 그럼에도불구하고 rating이 올랐다는거..;; -_-; 아 놔.. 이러면 다음에도 DIV1이잖아!!


[300] PointsOnCircle

원의 반지름이 들어오고 이 원 둘레에 놓이는 lattice point(x, y 좌표가 다 정수)의 개수를 구하는 문제..
문제에 보면 공식이 나와있다.. 공식은 r^2의 약수중에 4n+1 꼴의 약수의 개수에서 4n+3꼴의 약수의 개수를 빼면 된다.. 근데.. 계산하기 만만치 않을거같은데.. 우선 다른사람 소스를 보면서 이해해보아야겠다..

match editorial을 참고했다..

Note that we don't care about even divisors so divide r by 2 while r is even.
Find all the divisors of r using standard O(r1/2) algorithm and store them in an array v.
Note that a divisor of r2 has a form a*b where both a and b are the divisors of r.
Motivated by the third step, iterate through all pairs of elements of v (a, b) and check if we already encountered a divisor a*b (we store all previously encountered divisors in a set lookup). If not, check its remainder upon division by 4, increment respective counter (either for remainder 1, or remainder 3), and insert this divisor in lookup.

우리가 원하는 것은 r^2의 약수인데.. 그것을 구하기위해 우선 r의 약수들을 구한다 (sqrt(r)까지만 나눠보면 된다)..
이어서 "r^2의 약수 = 임의의 r의 약수 * 임의의 r의 약수" 라는 성질을 이용해서 r^2의 약수를 다 찾는다..
알고나면 간단한데.. 왜 문제풀땐 생각이 안날까.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <set>
      6 using namespace std;
      7
      8 class PointsOnCircle {
      9 public:
     10
     11 long long count(int n)
     12 {
     13     int i, j, size;
     14     long long cnt1, cnt3, temp;
     15     vector<long long> vt;
     16     set<long long> s;
     17     set<long long>::iterator it;
     18     for (i = 1; i*i <= n; i++) {
     19         if (n % i == 0) {
     20             vt.push_back(i);
     21             if (n / i != i)
     22                 vt.push_back(n/i);
     23         }
     24     }
     25     size = vt.size();
     26     for (i = 0; i < size; i++) {
     27         for (j = 0; j < size; j++) {
     28             s.insert(vt[i]*vt[j]);
     29         }
     30     }
     31     cnt1 = cnt3 = 0;
     32     for (it = s.begin(); it != s.end(); it++) {
     33         temp = *it;
     34         if (temp % 4 == 1)
     35             cnt1++;
     36         else if (temp % 4 == 3)
     37             cnt3++;
     38     }
     39     return 4 * (cnt1 - cnt3);
     40 }
     41
     42 };



[500] ArithmeticPrograssions

이 문제는 아직 읽어보지않았다.. 나중에 시간나면..



[1000] RelabelingOfGraph

graph가 주워지고 labeling하는 문제.. labeling하는 규칙은 우선순위가 높은것부터 하고 같은경우 숫자가 낮은 vertex부터 labeling한다.

UVa 11060 - Beverages 문제와 비슷한거같아서 소스를 조금 고쳐서 submit했는데.. system test에서 fail했다.. 음.. 내 생각에는 다 맞는거 같은데.. 뭐가 틀린것인가..?


음.. 뭐가 문제인지 찾아냈다..;;
서로 관계가 없는 vertex간에는 번호가 낮은 vertex를 먼저 labeling하는 줄 알았는데.. 그게 아니라 결과를 쭉 나열했을 때, 그게 lexicographically smallest가 되어야 한다는 것이었다..
결국 문제를 잘못 이해한거였다.. ㅠ_ㅠ 어쩐지.. UVa에서 AC받은게 fail일리 없지.. ㅠ_ㅠ

match editorial을 참조하여 풀었다..

우선 floyd warshall을 이용하여 transitive closure를 구하고 cycle이 있느지를 체크한다..
있으면 labeling을 할 수 없으므로 {} 을 return한다..

그 이외의 경우는 DFS를 통해서 역으로 호출하는데..
임의의 vertex u 에 대해서 v -> u 가 있으면 v 를 호출해가는 식이다..
이러한짓을 낮은 번호부터 하면 lexy smallest로 labeling이 된다..

  1 #include <iostream>
  2 #include <string>
  3 #include <cstdio>
  4 #include <map>
  5 #include <algorithm>
  6 #include <vector>
  7 using namespace std;
  8 //#define INF 99999999
  9
 10 int n;
 11 int graph[100][100];
 12 int check[100];
 13 int tcnt;
 14
 15 void dfs(int u)
 16 {
 17     int i;
 18     for (i = 0; i < n; i++) {
 19         if (graph[i][u] && check[i] == -1)
 20             dfs(i);
 21     }
 22     check[u] = tcnt++;
 23 }
 24
 25 class RelabelingOfGraph {
 26 public:
 27
 28 vector<int> renumberVertices(vector <string> m)
 29 {
 30     int i, j, k;
 31     char buf[100];
 32     vector<int> res;
 33
 34     res.clear();
 35     n = m.size();
 36     memset(graph, 0, sizeof(graph));
 37
 38     for (i = 0; i < n; i++) {
 39         strcpy(buf, m[i].c_str());
 40         for (j = 0; j < n; j++) {
 41             graph[i][j] = buf[j] - '0';
 42         }
 43     }
 44
 45     for (k = 0; k < n; k++) {
 46     for (i = 0; i < n; i++) {
 47     for (j = 0; j < n; j++) {
 48         if (graph[i][k] && graph[k][j])
 49             graph[i][j] = 1;
 50     }
 51     }
 52     }
 53
 54     for (i = 0; i < n; i++) {
 55         if (graph[i][i])
 56             return res;
 57     }
 58
 59     tcnt = 0;
 60     memset(check, -1, sizeof(check));
 61
 62     for (i = 0; i < n; i++) {
 63         if (check[i] == -1) {
 64             dfs(i);
 65         }
 66     }
 67
 68     for (i = 0; i < n; i++) {
 69         res.push_back(check[i]);
 70     }
 71     return res;
 72 }
 73
 74 };



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

TopCoder SRM 371 Div2 (완료)  (2) 2007.10.14
TopCoder SRM 370 Div2  (0) 2007.10.14
TopCoder SRM369 DIV2  (6) 2007.10.05
TopCoder SRM 368 Div 1  (0) 2007.10.03
TopCoder SRM 367 Div 2 (완료)  (10) 2007.09.27
TopCoder SRM 366 DIV 1  (2) 2007.09.18
TopCoder SRM 365 Div 1  (0) 2007.09.13
TopCoder SRM 364 Div 1  (0) 2007.09.09
TopCoder SRM 363 Div 2 (완료)  (0) 2007.08.12
TopCoder SRM 362 Div 2  (0) 2007.08.08
탑코더(TopCoder) 시작하기..  (0) 2007.08.07

Leave a Comment


to Top