저녁 8시에 열린 매치.. 평소에비해 한국사람도 무지 많았다.. 42명 참여.. 그중 중학생도 포함되어있었다..;; 근데 중학생들 실력이.. ㄷㄷㄷ 이제는 중학생들한테도 밀리는구나.. ㅠ_ㅠ

이번 매치는 무지 아쉬웠다.. 나름대로 문제셋이 쉬워서.. 처음으로 500점을 pass할 기회였는데.. 아쉽게도 시간이 모잘랐다.. 정말 1분만 더있었더라도 풀었을텐데.. 500점 pass했으면 난생처음 ACRush도 이겨보는건데 이런 좋은 기회를 놓치다니.. ㅠ_ㅠ;;;;

방 11등 전체 412등

사용자 삽입 이미지



[250] CountExpressions

input으로 x, y, val 이 주어지고 x 두개, y 두개 씩 사용하고 임의의 연산자 (+, -, *) 를 사용하여 수식을 만들때 수식의 결과가 val 이 되는 경우의 수 구하기..

우선 x, y를 두개씩 배열에 넣고 next_permutation을 이용하여 모든 operand의 sequence를 구한다.. 그리고 backtracking을 통하여 연산자를 대입..

이런 문제는 순식간에 풀어야되는데.. 흠..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int num[10];
  9 char path[10];
 10 int val1, cnt;
 11
 12 int cal(int x, char ch, int y)
 13 {
 14     if (ch == '+')
 15         return x+y;
 16     else if (ch == '-')
 17         return x-y;
 18     return x*y;
 19 }
 20
 21 void dfs(int u, char ch)
 22 {
 23     int k;
 24     path[u] = ch;
 25     if (u == 2) {
 26         k = num[0];
 27         k = cal(k, path[0], num[1]);
 28         k = cal(k, path[1], num[2]);
 29         k = cal(k, path[2], num[3]);
 30         if (k == val1)
 31             cnt++;
 32         return ;
 33     }
 34     dfs(u+1, '+');
 35     dfs(u+1, '-');
 36     dfs(u+1, '*');
 37 }
 38
 39 class CountExpressions {
 40 public:
 41
 42 int calcExpressions(int x, int y, int val)
 43 {
 44     if (x < y) {
 45         num[0] = num[1] = x;
 46         num[2] = num[3] = y;
 47     }
 48     else {
 49         num[0] = num[1] = y;
 50         num[2] = num[3] = x;
 51     }
 52     val1 = val;
 53     cnt = 0;
 54
 55     do {
 56         dfs(0, '+');
 57         dfs(0, '-');
 58         dfs(0, '*');
 59     } while (next_permutation(num, num+4));
 60 printf("cnt = %d\n", cnt);
 61     return cnt;
 62 }
 63
 64 };





[500] CountPaths

r by c 의 보드가 주어지고..  n개의 special field의 좌표가 주어진다.. (1, 1)에서 출발하여 (r, c)까지 가는데 0개의 SF를 지날때, 1개의 SF를 지날때, 2개의 SF를 지날때, ..., n개의 SF를 지날때 경우의 수를 각각 구하기.. 단 이동방향은 오른쪽 or 위쪽으로만 갈수있고 i > j 인 경우 i번째 SF를 지난 후 j번째 SF를 지날수 없다.. 즉, 반드시 input에 주어진 순서대로 지나야함..

이 문제는 대략 825 - Walking on the Safe Side 이런 류의 문제이다.. 여기에서 임의의 k개의 SF만 지날 경우와 번호가 높은 SF를 지난 후 번호가 낮은 SF를 지날 수 없다는 제약조건을 잘 생각해주면 된다..

결국 컴파일까지 해놓고 submit을 못했는데.. 그 코드에서 mod 연산만 추가하니 바로 pass해버렸다.. 무척 안타까운 문제. .ㅠ_ㅠ

4차원 DP로 풀었는데..
dp[i][j][k][l] = (i, j) 까지 갈때, k번째 SF까지 고려하여 l개의 SF를 지나는 경우의 수
라고 정의하고.. 대충 이리저리 시도해보니 답이 나왔다.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int n;
  9 int x[51], y[51];
 10 int dp[51][51][51][51];
 11
 12 int find_idx(int u, int v)
 13 {
 14     int i;
 15     for (i = 1; i <= n; i++) {
 16         if (x[i] == u && y[i] == v)
 17             break;
 18     }
 19     return i;
 20 }
 21
 22 class CountPaths {
 23 public:
 24
 25 vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol)
 26 {
 27     int i, j, k, l, p;
 28     vector<int> res;
 29     n = fieldrow.size();
 30     memset(dp, 0, sizeof(dp));
 31     for (i = 0; i <= n; i++) {
 32         dp[0][1][i][0] = 1;
 33     }
 34     for (i = 0; i < n; i++) {
 35         x[i+1] = fieldrow[i];
 36         y[i+1] = fieldcol[i];
 37     }
 38     for (i = 1; i <= r; i++) {
 39         for (j = 1; j <= c; j++) {
 40             p = find_idx(i, j);
 41             if (p == n+1) {
 42                 for (k = 0; k <= n; k++) {
 43                     for (l = 0; l <= k; l++) {
 44                         dp[i][j][k][l] = dp[i-1][j][k][l] + dp[i][j-1][k][l];
 45                         dp[i][j][k][l] %= 1000007;
 46                     }
 47                 }
 48             }
 49             else {
 50                 for (k = p; k <= n; k++) {
 51                     for (l = 1; l <= p; l++) {
 52                         dp[i][j][k][l] = dp[i][j-1][p-1][l-1] + dp[i-1][j][p-1][l-1];
 53                         dp[i][j][k][l] %= 1000007;
 54                     }
 55                 }
 56             }
 57         }
 58     }
 59
 60     for (i = 0; i <= n; i++) {
 61         dp[r][c][n][i] %= 1000007;
 62         res.push_back(dp[r][c][n][i]);
 63         printf("len %d = %d\n", i, dp[r][c][n][i]);
 64     }
 65     return res;
 66 }
 67
 68 };





[1000] MyFriends




to be updated..


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

TopCoder SRM 402 Div 1  (0) 2008.05.25
TopCoder SRM 401 Div1  (2) 2008.05.07
TopCoder SRM 400 Div 1  (0) 2008.05.02
리눅스에서 탑코더하기..  (0) 2008.05.01
TopCoder SRM 399 Div 1  (0) 2008.04.25
TopCoder SRM 398 Div1  (0) 2008.04.16
TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
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

Leave a Comment


to Top