좀 오래 지났지만 이제야 겨우 후기를 남기네..
아침 11시에 열렸던 매치.. 역시.. 첫문제부터 코딩에서 말리더니.. 결국 한문제도 못풀었다.. 흐미..
500점짜리 문제는 풀수 있었는데.. 상금매치도 다가오고.. 굳이 풀지 않았다..;; (핑계)
이렇게해서 별 소득없이.. 다시 Div2로 복귀 ㅠ_ㅠ;; 이제부터는 좀 열심히 해야지..!!
근데.. 밀려있는 문제.. 언제다풀지..????

방 16등 전체 367등..


[250] StreetWalking
walkTime은 건물을 한블럭 지나는데 걸리는 시간.. sneak는 건물을 대각선으로 가로질러 가는데 걸리는 시간일때.. (0, 0)에서 (x, y)까지 가는데 걸리는 최소시간 구하기..

음.. 실제 매치때는 괜히 어렵게 생각해서 못풀었다..
다음과 같이 나눠서 생각하면 쉽다..

1) sneakTime >= 2*walkTime -> 그냥 다 walk로만 다니면 된다..
2) walkTime <= sneakTime < 2*walkTime -> 최대한 sneak로 쭈욱 가다가 남은거는 walk로 간다..
3) wakTime > sneakTime -> 무조건 대각선으로만 가도록 노력한다.. (x+y) 가 짝수이면 sneak로만 다닐수 있지만 홀수이면 한번은 walk로 이동해야한다..

  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 class StreetWalking {
 10 public:
 11
 12 long long minTime(int X, int Y, int walkTime, int sneakTime)
 13 {
 14     long long sum;
 15     if (X > Y)
 16         X^=Y^=X^=Y;
 17     if (walkTime * 2 <= sneakTime) {
 18         sum = (long long)walkTime * X + (long long)walkTime * Y;
 19         return sum;
 20     }
 21     else if (walkTime <= sneakTime && walkTime * 2 > sneakTime) {
 22         sum = (long long)sneakTime * X + (long long)walkTime * (Y-X);
 23         return sum;
 24     }
 25     if ((X+Y) % 2 == 0) {
 26         sum = (long long)sneakTime * Y;
 27         return sum;
 28     }
 29     sum = (long long)sneakTime * (Y-1) + walkTime;
 30     return sum;
 31 }
 32
 33 };




[500] Skyscrapers

키가 모두 다른 n 명이 있을때, 왼쪽에서 보면 leftSide 만큼 보이고 오른쪽에서 보면 rightSide 만큼 보이도록 가능한경우의 수

이 문제는 매우 잘 알려진 문제이고 UVa 10128 - Queue 문제와 같다..
쉽게 DP 와 약간의 combinatoric 알고리즘을 이용해야 하지만..
쉽게 memoization 으로 푼 코드를 발견했다..

memo[n][left][right] = n 명이 남아있을때 왼쪽에서 left, 오른쪽에서 right 만큼 보이는 경우의 수..

  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 long long memo[101][101][101];
 13 int mod;
 14
 15 long long recur(int n, int left, int right)
 16 {
 17     long long res;
 18     if (n == 1) {
 19         if (left == 1 && right == 1)
 20             return 1;
 21         return 0;
 22     }
 23     if (n <= 0)
 24         return 0;
 25     if (left == 0 || right == 0)
 26         return 0;
 27     if (left > n || right > n)
 28         return 0;
 29     if (memo[n][left][right] != -1)
 30         return memo[n][left][right];
 31     /* 젤 작은거를 왼쪽에 두는 경우 +
 32        젤 작은거를 오른쪽에 두는 경우 +
 33        중간 아무데나 두는 경우
 34      */
 35     res = recur(n-1, left-1, right) + recur(n-1, left, right-1) + (n-2)*recur(n-1, left, right);
 36     res %= mod;
 37     return memo[n][left][right] = res;
 38 }
 39
 40 class Skyscrapers {
 41 public:
 42
 43 int buildingCount(int N, int leftSide, int rightSide)
 44 {
 45     long long res;
 46     memset(memo, -1, sizeof(memo));
 47     mod = 1000000007;
 48     res = recur(N, leftSide, rightSide);
 49     return (int)res;
 50 }
 51
 52 };




[900] PubTrivia



to be updated.


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

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
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 Online Round 1  (2) 2008.02.17

to Top