## SRM 501

오랜만에 회사에서 참가했다..
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 };

Level2 - FoxAverageSequence

1) A[i] <= (A + A + ... + 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 2011.05.20 2011.05.15 2011.04.27 2011.04.18 2011.04.01 2011.02.27 2011.02.02 2010.12.21 2010.12.09 2010.09.26