지난 화요일 저녁 9시에 열린 매치..
무려 세개의 SRM 을 띠어먹고 오랜만에 참여했는데.. 흠.. 좀 아쉬운 매치가 됐다..
250을 너무 늦게 풀어서 등수가 확 밀렸다.. ㅠ_ㅠ
500은 블챌을 했어도 몇개는 성공했을텐데.. 내꺼가 희안하게 챌 안당하길래.. 감격하고있다가 망했다..
비록 끝내 챌 당했지만 failed challenge 를 세개나 유도하는 등.. 소기의 목적을 달성했다..




Level1 - RabbitNumbering
n 개의 숫자가 각각 1 ~ maxNumber[i] (i = 0...n-1) 까지의 범위중에 하나를 가질 수 있다..
각 범위당 1개의 수를 뽑아서 n 개의 distinct 한 숫자를 뽑으려고 할때 몇가지 방법이 있을지..

아직도 잘 이해는 안되지만..
sort 해놓고서 result = result * (maxNumber[i] - i) 를 하면 된다..
물론 maxNumber[i] - i 가 중간에 0보다 작거나 같아지면 답이 없다..

다른사람들이 다 빨리 풀길래.. 나도 그냥 눈치껏 이렇게 풀었는데.. 흠.. 이해안됨.. -_-

  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 class RabbitNumbering {
 13 public:
 14
 15 int theCount(vector <int> num)
 16 {
 17     int n;
 18     int i, j;
 19     long long sum;
 20     sort(num.begin(), num.end());
 21     n = num.size();
 22     sum = 1;
 23     for (i = 0, j = 0; i < n; i++, j++) {
 24         sum *= (long long)(num[i] - j);
 25         sum %= 1000000007LL;
 26     }
 27     return sum;
 28 }
 29
 30 };



Level2 - Nisoku
1.5 ~ 10 사이의 수 n 개가 들어오는데.. 임의의 두 수를 뽑아서 곱하거나 또는 더할 수 있다..
이 과정을 한개의 수가 남을 때까지 반복할때 마지막에 남는 수를 최대화하기..

match editorial 을 보고 풀었다..
일단 임의의 pair 를 곱하냐 더하냐 를 정해야하는데..
어떤 수가 3 보다 커지면 무조건 곱하는게 좋다..
즉, 모든 수에 대해서 최대 1번만 더하면 된다..

만약에 2개의 쌍을 더한다고 해보자.. 어떻게 pairing 하는게 좋을까..?
sort 한 순서대로 a, b, c, d 가 있을 경우
(a, d), (b, c) 이런식올 pairing 하는게 좋다..
a, b, c, d, e, f 라면.. (a, f), (b, e), (c, d) 이런 식이 되겠다..

따라서 더해야 할 쌍을 0, 2, 4, 6, ..., n 일때 각각 값을 구해서 그 중 최대값을 구하면 된다..
사실 n 까지 해볼것도 없고.. k-1 번째가 2.0 보다 작은 k 번째 까지만 하면 될것같기도 한데.. 과연 될까..? -_-?

  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 class Nisoku {
 13 public:
 14
 15 double theMax(vector <double> cards)
 16 {
 17     int n;
 18     int i, j, k;
 19     double max1, sum;
 20     n = cards.size();
 21     sort(cards.begin(), cards.end());
 22     max1 = 0;
 23     for (i = 0; i <= n; i += 2) {
 24         sum = 1;
 25         for (j = 0, k = i-1; j < i / 2; j++, k--) {
 26             sum *= cards[j] + cards[k];
 27         }
 28         for (j = i; j < n; j++) {
 29             sum *= cards[j];
 30         }
 31         if (sum > max1)
 32             max1 = sum;
 33     }
 34     return max1;
 35 }
 36
 37 };



Level3 - RabbitPuzzle


to be updated..



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

SRM 469  (0) 2010.05.05
[SRM 468] 보람이 없구만..  (0) 2010.04.21
SRM 466  (0) 2010.04.05
TopCoder Open 2010 일정..  (0) 2010.03.31
SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20
TopCoder SRM 458 Div 1  (0) 2010.01.17
TopCoder SRM 457 Div 1  (0) 2010.01.06
[SRM 456] 2009년 마지막 SRM  (0) 2009.12.23
TopCoder SRM 455 Div 1  (0) 2009.12.19

Comments

  1. Toivoa 2010.03.07 10:11 Permalink Modify/Delete Reply

    easy에서 non-decreasing order로 소트를 하고 나면, 앞에서 선택된 숫자들은 항상 뒤에서 선택할 수 있는 숫자 범위 안에 들어가기 때문입니다.

Leave a Comment


to Top