## TopCoder SRM 398 Div1

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

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

방 11등 전체 412등 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;
9 char path;
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;
27         k = cal(k, path, num);
28         k = cal(k, path, num);
29         k = cal(k, path, num);
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 = num = x;
46         num = num = y;
47     }
48     else {
49         num = num = y;
50         num = num = 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 };

 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, y;
10 int dp;
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[i] = 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 };

 MyFriends

to be updated..

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

 TopCoder SRM 402 Div 1  (0) 2008.05.25 2008.05.07 2008.05.02 2008.05.01 2008.04.25 2008.04.16 2008.04.13 2008.04.09 2008.03.24 2008.03.12 2008.03.07