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

to Top