TCO08 R1.. 새벽 3시에 열렸는데.. 뭐 힘한번 못써보고 삽질만 하다가 결국 탈락.. 허무하다.. ㅠ_ㅠ
문제가 좀 어려웠는데.. 결론적으로 다 나의 실력 부족이었다.. 내년에는 R1 통과를 목표로 열심히 준비해야겠다..

앗.. 그런데 이제보니 우리나라가 9위네.. 앞서있던 크로아티아를 밀어내고.. 네덜란드와 접전중..;

방 24등(최하위 ㅠ_ㅠ;;) 전체 1390등..


사용자 삽입 이미지



[250] DiscountCombination
input으로 사고자하는 물건의 가격과.. 기타 다른 물건의 가격이 주어진다.. 기타 다른 물건을 사면 최대 1%에서 3%까지 원래 사고자하는 물건의 가격을 깎아준다.. 사고자하는 물건을 가장 싸게 얼마에 살 수 있는지 구하는 문제..

흠.. 생각보다 쉽지않은 문제였다.. 대회중에 우선 모든 경우를 다 따져봐야 한다고 생각했는데.. input이 50이라 O(2^50) = TLE 그래서 다른사람들도 나름대로 빨리 풀고있고.. 뭔가 쉬운방법이 있을것같아서 greedy하게 생각했는데.. 우선 샀을경우 가격을 낮추는 상품은 모두 골랐다.. 당연히 답이 나오면 안되는데 sample이 다 통과하길래 그냥 submit.. 나중에 여유가 있고 다른게 떠오르면 resubmit하려고했는데.. 그럴 기회가 없었다..;; 젠장.. 결국 challenge fail.. 정말 오랜만에 챌당해보았다..

솔루션은 match editorial을 참고했다..

우선 모든 경우를 다 search해야하는것은 맞다.. 그러나 해당하는 discount가 1, 2, 3% 밖에 없다는 것을 감안하여.. 상품들은 세개의 셋으로 구분한다.. 각 셋에대해서 discount 비율이 같으므로 무조건 싼것부터 사야한다.. 즉, 더 비싼것을 사고 싼것을 않사는 경우는 최적이 될 수 없다는 점을 이용하여 pruning 한다.

매치중에 나한테는 생각하기 힘든 문제였다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8
  9 int d[4][100];
 10
 11 int comp(const void* x, const void* y)
 12 {
 13     int* a = (int*)x;
 14     int* b = (int*)y;
 15     return (*a) - (*b);
 16 }
 17
 18 class DiscountCombination {
 19 public:
 20
 21 double minimumPrice(vector <string> discounts, int price)
 22 {
 23     int n;
 24     int i, j, k, l;
 25     int a, b;
 26     int cnt1, cnt2, cnt3;
 27     char buf[100];
 28     double sum, min1;
 29
 30     n = discounts.size();
 31     cnt1 = cnt2 = cnt3 = 0;
 32     for (i = 0; i < n; i++) {
 33         strcpy(buf, discounts[i].c_str());
 34         sscanf(buf, "%d%d", &a, &b);
 35         if (b == 1) {
 36             d[1][cnt1] = a;
 37             cnt1++;
 38         }
 39         else if (b == 2) {
 40             d[2][cnt2] = a;
 41             cnt2++;
 42         }
 43         else {
 44             d[3][cnt3] = a;
 45             cnt3++;
 46         }
 47     }
 48
 49     qsort(d[1], cnt1, sizeof(int), comp);
 50     qsort(d[2], cnt2, sizeof(int), comp);
 51     qsort(d[3], cnt3, sizeof(int), comp);
 52
 53     min1 = price;
 54     for (i = 0; i <= cnt1; i++) {
 55     for (j = 0; j <= cnt2; j++) {
 56     for (k = 0; k <= cnt3; k++) {
 57         sum = 0.0;
 58         for (l = 0; l < i; l++) {
 59             sum += d[1][l];
 60         }
 61         for (l = 0; l < j; l++) {
 62             sum += d[2][l];
 63         }
 64         for (l = 0; l < k; l++) {
 65             sum += d[3][l];
 66         }
 67         sum += price * pow(0.99, (double)i) * pow(0.98, (double)j) * pow(0.97, (double)k);
 68         if (sum < min1) {
 69             min1 = sum;
 70         }
 71     }
 72     }
 73     }
 74     return min1;
 75 }
 76
 77 };




[500] Chomp
가로가 N, 세로가 3인 보드가 주어진다.. 임의의 지점 (i, j)를 선택하면 (i, j) cell을 포함하여 우측 위방향 (1사분면)을 제거한다.. 이와 같은 방법으로 서로 번갈아가면서 cell을 제거해나갈때 가장 왼쪽 아래 (1, 1) cell 을 take하는 사람이 지게된다.. 첫번째 플레이어가 이기는경우 최소 몇번만에 이기는지.. 진다면 최대 몇번만에 지는지 구하는 문제..

게임이론을 이용하여 풀 수 있다.. 현재 상태에서 갈 수 있는 상태가 모두 이기는 상태이면 현재 상태는 지는 상태이고.. 지는 상태로 갈 수 있는 경우가 하나라도 있으면 현재 상태는 이기는 상태이다..

첫번째(바닥)줄의 cell이 a개 두번째(가운데)줄의 cell이 b개 세번째(맨위)줄의 cell이 c개일때.. 상태를 (a, b, c)로 나타낼 수 있다.. 이 상태에서 모든 가능한 경우를 다 고려해서 다음 상태로 넘어가면 된다.. recursion + memo로 쉽게 풀 수 있다..

아.. 이 매치가 올해 2월에 열렸는데.. 이제야(2008-11-30) 이 문제를 해결했구나.. ㅠ_ㅠ 좋은문제..

  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
  9 int memo[101][101][101];
 10
 11 /*
 12 XXXXXXXXX       <--- c 개
 13 XXXXXXXXXXX     <--- b 개
 14 XXXXXXXXXXXXX   <--- a 개
 15 */
 16 int recur(int a, int b, int c)
 17 {
 18     int res, i, x;
 19
 20     if (memo[a][b][c])
 21         return memo[a][b][c];
 22     if (a == 1 && b == 0 && c == 0)
 23         return memo[a][b][c] = -1;
 24
 25     res = -1;
 26     for (i = 1; i < a; i++) {
 27         x = recur(i, min(i, b), min(i, c));
 28         if (x < 0) {
 29             if (res < 0)
 30                 res = 1-x;
 31             else
 32                 res = min(res, 1-x);
 33         }
 34         else {
 35             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 36             if (res < 0)
 37                 res = min(res, -x-1);
 38         }
 39     }
 40     for (i = 0; i < b; i++) {
 41         x = recur(a, i, min(i, c));
 42         if (x < 0) {
 43             if (res < 0)
 44                 res = 1-x;
 45             else
 46                 res = min(res, 1-x);
 47         }
 48         else {
 49             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 50             if (res < 0)
 51                 res = min(res, -x-1);
 52         }
 53     }
 54     for (i = 0; i < c; i++) {
 55         x = recur(a, b, i);
 56         if (x < 0) {
 57             if (res < 0)
 58                 res = 1-x;
 59             else
 60                 res = min(res, 1-x);
 61         }
 62         else {
 63             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 64             if (res < 0)
 65                 res = min(res, -x-1);
 66         }
 67     }
 68     return memo[a][b][c] = res;
 69 }
 70
 71 class Chomp {
 72 public:
 73
 74 int moves(int N)
 75 {
 76     memset(memo, 0, sizeof(memo));
 77     return recur(N, N, N);
 78 }
 79
 80 };



[1000] BoxFilling



to be updated..

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

SRM 395 Div1  (0) 2008.04.09
TopCoder SRM 394 Div 1  (2) 2008.03.24
흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27
TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 388 Div1  (2) 2008.01.16

to Top