아침 10시에 열린 매치.. 결과는 역시.. -_-;; 흠.. 250점짜리 쉬운문제였는데 너무 안일하게 생각해서.. 결국 system fail..;; 아쉽군.. 쩝.. 그런데 0점을 기록했는데도 불구하고 rating은 소폭 올랐다.. 음.. 이런경우도 있군..

방 9등 전체 220등..

사용자 삽입 이미지



[250] AvoidingProduct
자연수로 이루어진 set과 n 이 주어지고 |n - (x*y*z)| 이 최소가 되는 x, y, z를 찾는 문제.. 단 x, y, z은 주어진 set에 있는 수일 수 없다..


to be updated..




[500] BinarySum
a, b, c 가 주어질 때, a, b, c를 2진수로 나타내어 bit를 reordering 할 수 있다.. (심지어 leading zero도 가능하다) 이렇게 만들어진 수를 각각 a', b', c' 라고 할 때, a' + b' = c' 를 만족하는 가장 작은 c' 를 구하기..

match editorial을 참고하여 풀었다..~
이 문제는 DP로 풀 수 있는데..

dp[n][a][b][c][carry] = n자리까지 a개의 1, b개의 1, c개의 1을 사용하여 만들 수 있는 가장 작은 수

이런식으로 정의하면..

a의 다음 bit가 0 일 경우, 1일경우, b의 다음 bit가 0일 경우, 1일 경우.. 로 나눠서
다음과 같은 점화식을 만들 수 있다..

dp[n][a][b][c][carry] = min(
2 * dp[n-1][a-1][b][c-(carry+1)%2][(carry+1)/2] + (carry+1)%2,
2 * dp[n-1][a][b-1][c-(carry+1)%2][(carry+1)/2] + (carry+1)%2,
..
..
)

  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 999999999999999999LL
 10 #define LL long long
 11
 12 LL memo[32][32][32][32][2];
 13
 14 int get_len(LL a)
 15 {
 16     int cnt;
 17     cnt = 0;
 18     while (a) {
 19         cnt++;
 20         a >>= 1;
 21     }
 22     return cnt;
 23 }
 24
 25 int get_bit(LL a)
 26 {
 27     int cnt;
 28     cnt = 0;
 29     while (a) {
 30         if (a & 1)
 31             cnt++;
 32         a >>= 1;
 33     }
 34     return cnt;
 35 }
 36
 37 LL recur(int n, int a, int b, int c, int carry)
 38 {
 39     int x, y, z, new_carry;
 40     LL res, temp;
 41     if (a < 0 || b < 0 || c < 0)
 42         return INF;
 43     if (memo[n][a][b][c][carry] != -1)
 44         return memo[n][a][b][c][carry];
 45     res = INF;
 46     if (n == 0) {
 47         if (a == 0 && b == 0 && c == 0 && carry == 0)
 48             res = 0;
 49         else
 50             res = INF;
 51         return memo[n][a][b][c][carry] = res;
 52     }
 53     for (x = 0; x < 2; x++) {
 54         for (y = 0; y < 2; y++) {
 55             z = x + y + carry;
 56             new_carry = 0;
 57             if (z >= 2) {
 58                 z -= 2;
 59                 new_carry++;
 60             }
 61             temp = 2 * recur(n-1, a-x, b-y, c-z, new_carry) + z;
 62             res = min(res, temp);
 63         }
 64     }
 65     return memo[n][a][b][c][carry] = res;
 66 }
 67
 68 class BinarySum {
 69 public:
 70
 71 int rearrange(int a, int b, int c)
 72 {
 73     int n;
 74     LL res;
 75     n = max(get_len(a), max(get_len(b), get_len(c)));
 76     memset(memo, -1, sizeof(memo));
 77     res = recur(n, get_bit(a), get_bit(b), get_bit(c), 0);
 78     if (res == INF)
 79         return -1;
 80     return (int)res;
 81 }
 82
 83 };



[1000] DancingParty



to be updated..

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

TopCoder SRM 404 Div 1  (2) 2008.06.06
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

Leave a Comment


to Top