어제 새벽 1시에 열린 매치..
SRM 이 한달에 3번으로 늘어서.. 이거 좀 자주 돌아온다..
이번 매치에서는 정말 오랜만에 어처구니없는 실수를 하면서
진짜 쉬운 250을 놓쳤다.. 흠.. 이런일이 근래에 없었는데..
덕푼에 rating 100점 넘게 폭락.. 쩝..
방도 짜증나게 red가 7명이나 있는 5번방에 걸리고.. 제발 20번 이상에 좀 걸려라..
작년 여름부터 시작된 슬럼프가 지금까지 이어지는중..





Level1 - Inequalities
여러개의 조건이 주어진다.. 적어도 하나이상의 수가(정수일필요는 없음) 존재하도록 최대한 많은 조건을 선택하기..

단순히 모든 X 에 대해서 시도해봤다..
C 가 0 ~ 1000 사이의 정수이므로 X 를 0.5 씩 증가시키면서 -0.5 부터 1000.5 까지만 확인하면 된다..
이 문제를 틀린 이유는.. 루프를 한번 덜 돌렸다.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 //#define INF 999999999
 11 #define EPS 1e-14
 12
 13 class Inequalities {
 14 public:
 15
 16 int maximumSubset(vector <string> ine)
 17 {
 18     int n;
 19     int i, j;
 20     int c, cnt, max1;
 21     double a;
 22     char buf[100], buf2[100];
 23     n = ine.size();
 24     max1 = 0;
 25     for (a = -0.5; a < 2002; a += 0.5) {
 26         cnt = 0;
 27         for (j = 0; j < n; j++) {
 28             sscanf(ine[j].c_str(), "%s %s %d", buf, buf2, &c);
 29             if (!strcmp(buf2, "<")) {
 30                 if (fabs(a-c) < EPS || a > c) ;
 31                 else
 32                     cnt++;
 33             }
 34             else if (!strcmp(buf2, "<=")) {
 35                 if (fabs(a-c) < EPS || a < c)
 36                     cnt++;
 37             }
 38             else if (!strcmp(buf2, "=")) {
 39                 if (fabs(a-c) < EPS)
 40                     cnt++;
 41             }
 42             else if (!strcmp(buf2, ">=")) {
 43                 if (fabs(a-c) < EPS || a > c)
 44                     cnt++;
 45             }
 46             else if (!strcmp(buf2, ">")) {
 47                 if (fabs(a-c) < EPS || a < c) ;
 48                 else
 49                     cnt++;
 50             }
 51         }
 52         max1 = max(cnt, max1);
 53     }
 54     return max1;
 55 }
 56
 57 };



Level2 - NumberPyramids

위에 숫자는 아래 두개의 숫자의 합이다.. 꼭대기에 들어갈 수와 밑바닥의 길이가 주어질때 만들 수 있는 피라미드의 개수 구하기

문제를 조금 연구해보면

top = c1 * x1 + c2 * x2 + ... + cn * xn 이 되는데..
여기서 (c1, c2, ..., cn) 은 놀랍게도 binomial coefficient 가 된다..

dp[top] = 위의 식에서 나올 수 있는 (x1, x2, ..., xn) 의 개수
라고 정의하고 DP 로 풀면 되겠다..~

좋은 문제..~

  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 #define MOD 1000000009
 13 #define MAXN 51
 14
 15 int dp[1000001];
 16
 17 /* combi[n][r] = n C r */
 18 long long combi[MAXN][MAXN];
 19 void init_combi()
 20 {
 21     int i, j;
 22     for (i = 0; i < MAXN; i++) {
 23         combi[i][i] = 1;
 24         combi[i][0] = 1;
 25     }
 26     for (i = 0; i < MAXN; i++) {
 27         for (j = 1; j < i; j++) {
 28             combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
 29         }
 30     }
 31 }
 32
 33 class NumberPyramids {
 34 public:
 35
 36 int count(int baseLength, int top)
 37 {
 38     int i, j;
 39
 40     if (baseLength > 20 || top < (1 << baseLength-1))
 41         return 0;
 42     top -= (1 << baseLength-1);
 43
 44     init_combi();
 45
 46     memset(dp, 0, sizeof(dp));
 47     dp[0] = 1;
 48
 49     for (i = 0; i < baseLength; i++) {
 50         for (j = combi[baseLength-1][i]; j <= top; j++) {
 51             dp[j] += dp[j-combi[baseLength-1][i]];
 52             dp[j] %= MOD;
 53         }
 54     }
 55     return dp[top];
 56 }
 57
 58 };



Level3 - TheContest


to be updated..


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

[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
TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07

Leave a Comment


to Top