## SRM 501

Problem Solving/TopCoder logs 2011. 4. 1. 21:27

오랜만에 회사에서 참가했다..

500 이 나름 쉬운게 나왔는데 점화식까지 찾았는데 코딩이 늦는바람에 결국 서밋 실패했다..

나이를 먹어서 그런지.. 계속 코딩속도가 느려지고있다.. ㅠ_ㅠ;;

250 도 그닥 만족스럽지 못하게 풀었는데.. 좀 틀려주는 사람이 많아서 rating 을 조금 올렸다..~

yellow 턱밑까지 올라오긴 했는데.. 쩝

Level1 - FoxPlayingGame

scoreA 를 nA 번 add, scoreB 를 nB 번 multiply 해서 얻을 수 있는 최대값 구하기..

이 문제는 DP로 복잡하게 푼 사람이 많던데.. greedy 로 풀 수 있다는 것만 간파하면 매우 간단히 풀 수 있다..

일단 더하기 연산부터 다 하고,

곱하기를 0번 적용, 1번 적용, 2번 적용, ... nB번 적용 .. 한것중에 최대값을 구하면 된다..

왜 그럴까..?

Level2 - FoxAverageSequence

1) A[i] <= (A[0] + A[1] + ... + A[i-1]) / i

2) there must be no index i, 0 <= i < N-2, such that A[i] > A[i+1] > A[i+2]

요 두 조건을 만족하는 가능한 seq 의 개수 구하기..

Level3 - FoxSearchingRuins

to be updated..

500 이 나름 쉬운게 나왔는데 점화식까지 찾았는데 코딩이 늦는바람에 결국 서밋 실패했다..

나이를 먹어서 그런지.. 계속 코딩속도가 느려지고있다.. ㅠ_ㅠ;;

250 도 그닥 만족스럽지 못하게 풀었는데.. 좀 틀려주는 사람이 많아서 rating 을 조금 올렸다..~

yellow 턱밑까지 올라오긴 했는데.. 쩝

Level1 - FoxPlayingGame

scoreA 를 nA 번 add, scoreB 를 nB 번 multiply 해서 얻을 수 있는 최대값 구하기..

이 문제는 DP로 복잡하게 푼 사람이 많던데.. greedy 로 풀 수 있다는 것만 간파하면 매우 간단히 풀 수 있다..

일단 더하기 연산부터 다 하고,

곱하기를 0번 적용, 1번 적용, 2번 적용, ... nB번 적용 .. 한것중에 최대값을 구하면 된다..

왜 그럴까..?

1 #include <iostream>

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <queue>

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 9999999999999.0

11 //#define EPS 1e-14

12

13 class FoxPlayingGame {

14 public:

15

16 double theMax(int nA, int nB, int paramA, int paramB)

17 {

18 double sa, sb;

19 double sum, max1;

20 int i, j;

21 sa = (double)paramA / 1000.0;

22 sb = (double)paramB / 1000.0;

23 max1 = -INF;

24 for (i = 0; i <= nB; i++) {

25 sum = 0;

26 for (j = 0; j < i; j++) {

27 sum *= sb;

28 }

29 for (j = 0; j < nA; j++) {

30 sum += sa;

31 }

32 for (j = i; j < nB; j++) {

33 sum *= sb;

34 }

35 printf("i = %d, sum = %lf\n", i, sum);

36 if (sum > max1)

37 max1 = sum;

38 }

39 return max1;

40 }

41

42 };

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <queue>

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 9999999999999.0

11 //#define EPS 1e-14

12

13 class FoxPlayingGame {

14 public:

15

16 double theMax(int nA, int nB, int paramA, int paramB)

17 {

18 double sa, sb;

19 double sum, max1;

20 int i, j;

21 sa = (double)paramA / 1000.0;

22 sb = (double)paramB / 1000.0;

23 max1 = -INF;

24 for (i = 0; i <= nB; i++) {

25 sum = 0;

26 for (j = 0; j < i; j++) {

27 sum *= sb;

28 }

29 for (j = 0; j < nA; j++) {

30 sum += sa;

31 }

32 for (j = i; j < nB; j++) {

33 sum *= sb;

34 }

35 printf("i = %d, sum = %lf\n", i, sum);

36 if (sum > max1)

37 max1 = sum;

38 }

39 return max1;

40 }

41

42 };

Level2 - FoxAverageSequence

1) A[i] <= (A[0] + A[1] + ... + A[i-1]) / i

2) there must be no index i, 0 <= i < N-2, such that A[i] > A[i+1] > A[i+2]

요 두 조건을 만족하는 가능한 seq 의 개수 구하기..

Level3 - FoxSearchingRuins

to be updated..

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

SRM 507 - 나이스! (0) | 2011.05.30 |
---|---|

TCO11 Qual2 (0) | 2011.05.20 |

TCO11 Qual1 (2) | 2011.05.15 |

SRM 504 - unrated event (0) | 2011.04.27 |

SRM 503 흑흑 ㅠ_ㅠ;; (0) | 2011.04.18 |

SRM 498 - WTF!! (0) | 2011.02.27 |

SRM 496 (2) | 2011.02.02 |

SRM 491 - Blue 복귀.. (0) | 2010.12.21 |

SRM 490 - Yellow 1차 방어전 성공.. (0) | 2010.12.09 |

SRM 483 - 처음으로 Petr 이겨본 매치..~ (0) | 2010.09.26 |