지난 수요일 밤 12시에 열린 매치
와.. 이거 250이 250이 아닌데.. -_-
코딩시간 내내 삽질만 하다가 결국 250도 코딩을 완료하지 못하고 끝났다.. ㅠ_ㅠ
그래도 오랜만에 블챌 하나 성공시켜서 레이팅을 조금 올렸다..
역시.. 가장 마지막에 급하게 서밋한애를 챌한다는 기본적인 원칙이 맞아 떨어졌다..


오오.. 50등 안에 7명이나 들다니.. 한국사람들의 선전이 대단한데..~~

참고로.. division summary 중에.. 이런 결과가 나오기 참 쉽지 않은데.. Burunduk1 완전 대박.. -_-;;;;


Level1 - ColorfulStrings
모든 substring에 대해서 각 digit의 곱이 다 다를 때 colorful 이라고 한다. 길이 n 짜리 colorful string 중에 k 번째 구하기..

처음에 문제 열고 당황한 문제.. 그런데 곰곰히 생각해보니 n 이 9보다 큰 경우 항상 답이 없다..
따라서 n 이 최대 8이라고 생각하고 backtracking 을 시도할 수 있다..
실제 매치때 위 트릭을 너무 늦게 간파해서.. 결국 코딩을 완료하지 못했다..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 int n, k;
 13 string sol;
 14 int path[100];
 15 int cnt[10000000];
 16
 17 int dfs(int u)
 18 {
 19     int i, j;
 20     int p;
 21     int fl;
 22     if (u == n) {
 23         k--;
 24         if (k == 0) {
 25             for (i = 0; i < n; i++) {
 26                 sol += (char)(path[i]+'0');
 27             }
 28             return 1;
 29         }
 30         return 0;
 31     }
 32
 33     for (i = 0; i < 10; i++) {
 34         fl = 1;
 35         p = 1;
 36         path[u] = i;
 37         for (j = u; j >= 0; j--) {
 38             p *= path[j];
 39             cnt[p]++;
 40             if (cnt[p] > 1)
 41                 fl = 0;
 42         }
 43         if (fl) {
 44             if (dfs(u+1))
 45                 return 1;
 46         }
 47         p = 1;
 48         for (j = u; j >= 0; j--) {
 49             p *= path[j];
 50             cnt[p]--;
 51         }
 52     }
 53     return 0;
 54 }
 55
 56 class ColorfulStrings {
 57 public:
 58
 59 string getKth(int N, int K)
 60 {
 61     n = N;
 62     k = K;
 63     sol = "";
 64     if (N > 9)
 65         return "";
 66     memset(cnt, 0, sizeof(cnt));
 67     if (dfs(0)) {
 68         return sol;
 69     }
 70     return "";
 71 }
 72
 73 };



Level2 - ColorfulDecoration

xa 또는 xb, ya 또는 yb 중 하나만 선택해서 (x, y) 좌표를 중심으로하는 정사각형을 만든다
크기가 같은 n 개의 정사각형을 만들때 side 의 크기를 최대화하기..

매우 좋으면서 어려운 문제..
일단 정사각형 side 의 크기는 binary search 로 검사한다..
그리고나서 그게 가능한지 확인해야되는데 이는 2-SAT problem 이 된다..

A or B 의 관계가 있을 때, ~A -> B, ~B -> A 로 edge 를 연결하고..
~A 와 A 가 함께 포함되는 SCC 가 있는지 살펴보면 된다..~
아.. 어렵다.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 int n;
 13 char graph[300][300];
 14
 15 int get_neg(int u)
 16 {
 17     if (u < n)
 18         return u + n;
 19     return u - n;
 20 }
 21
 22 class ColorfulDecoration {
 23 public:
 24
 25 int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb)
 26 {
 27     long long left, right, mid, res;
 28     int i, j, k;
 29     int fl;
 30     int x1, y1, x2, y2;
 31     n = xa.size();
 32     left = 0;
 33     right = 4000000000LL;
 34     res = 0;
 35     while (left <= right) {
 36         mid = (left + right) / 2;
 37         memset(graph, 0, sizeof(graph));
 38         for (i = 0; i < n+n; i++) {
 39             for (j = 0; j < n+n; j++) {
 40                 if (i == j || i == get_neg(j))
 41                     continue;
 42                 if (i < n) {
 43                     x1 = xa[i];
 44                     y1 = ya[i];
 45                 }
 46                 else {
 47                     x1 = xb[i-n];
 48                     y1 = yb[i-n];
 49                 }
 50                 if (j < n) {
 51                     x2 = xa[j];
 52                     y2 = ya[j];
 53                 }
 54                 else {
 55                     x2 = xb[j-n];
 56                     y2 = yb[j-n];
 57                 }
 58                 /* (i or j) */
 59                 if (abs(x1-x2) < mid && abs(y1-y2) < mid) {
 60                     graph[get_neg(i)][j] = 1;
 61                     graph[get_neg(j)][i] = 1;
 62                 }
 63             }
 64         }
 65         for (k = 0; k < n+n; k++) {
 66         for (i = 0; i < n+n; i++) {
 67         for (j = 0; j < n+n; j++) {
 68             if (graph[i][k] && graph[k][j])
 69                 graph[i][j] = 1;
 70         }
 71         }
 72         }
 73         fl = 1;
 74         for (i = 0; i < n; i++) {
 75             if (graph[i][get_neg(i)] && graph[get_neg(i)][i]) {
 76                 fl = 0;
 77                 break;
 78             }
 79         }
 80         if (fl) {
 81             left = mid + 1;
 82             res = mid;
 83         }
 84         else {
 85             right = mid - 1;
 86         }
 87     }
 88     return (int)res;
 89 }
 90
 91 };



Level3 - ColorfulMaze


to be updated..


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

TCO10 Qaul2  (2) 2010.05.13
SRM 469  (0) 2010.05.05
[SRM 468] 보람이 없구만..  (0) 2010.04.21
SRM 466  (0) 2010.04.05
TopCoder Open 2010 일정..  (0) 2010.03.31
SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20
TopCoder SRM 458 Div 1  (0) 2010.01.17
TopCoder SRM 457 Div 1  (0) 2010.01.06
[SRM 456] 2009년 마지막 SRM  (0) 2009.12.23

Leave a Comment


to Top