새벽 2시에 있었던 매치.. 역대 SRM중에 가장 성적이 좋았다.. 음.. 혹시 내가 새벽 2시에 가장 컨디션이 좋은건가.. -_-? 음.. 이번 매치는 실력보다는 문제가 좀 도와준면이 있다.. 오랜만에 챌도 성공시키고 (4개시도 3개성공) rating도 많이 높아졌고 volatality도 많이 높아졌다.. 올해안에 DIV1으로 올라갈 가능성을 열었다..

방 1등 전체 8등


사용자 삽입 이미지
방 1등.. 얼마만인가..

사용자 삽입 이미지
rating을 150 이상 올렸다.. 역대 최고의 상승폭..




[250] TheBestName
단순히 이름을 sort하는 문제이다.. "JOHN"이란 이름이 무조건 제일 앞에와야하고..(문제 출제자가 John인듯 싶다.. -_-) 나머지는 각 문자의 합이 클수록 앞에와야 한다.. 같을경우는 사전순으로..

그냥 sorting하면 된다.. 처음에 vector를 그대로 sort하려고했는데 자꾸 컴파일에러가 나서 다시 char* 배열로 바꾸고 qsort를 사용하였다.. 허허.. 이게 왠 삽질이냐.. stl sort 문법이 가물가물하다.. ㅠ_ㅠ 그런데도 방에서 이문제를 4번째로 풀었다니 놀라울따름..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 int comp(const void* a, const void* b)
      9 {
     10     char str1[1000], str2[1000];
     11     int len1, len2;
     12     int sum1, sum2;
     13     int i;
     14     strcpy(str1, (char*)a);
     15     strcpy(str2, (char*)b);
     16     if (!strcmp(str1, "JOHN"))
     17         return -1;
     18     if (!strcmp(str2, "JOHN"))
     19         return 1;
     20
     21     len1 = strlen(str1);
     22     len2 = strlen(str2);
     23     sum1 = sum2 = 0;
     24     for (i = 0; i < len1; i++) {
     25         sum1 += str1[i]-'A'+1;
     26     }
     27     for (i = 0; i < len2; i++) {
     28         sum2 += str2[i]-'A'+1;
     29     }
     30     if (sum1 != sum2)
     31         return sum2 - sum1;
     32     return strcmp(str1, str2);
     33 }
     34
     35 class TheBestName {
     36 public:
     37
     38 vector <string> sort(vector <string> names)
     39 {
     40     vector<string> res;
     41     char str[100][1000];
     42     int i;
     43     for (i = 0; i < names.size(); i++) {
     44         strcpy(str[i], names[i].c_str());
     45     }
     46     qsort(str, names.size(), 1000, comp);
     47     for (i = 0; i < names.size(); i++) {
     48         res.push_back(str[i]);
     49     }
     50     return res;
     51 }
     52
     53 };




[500] TheDiceGame

주사위를 던져서 나온 수 만큼 candy를 얻는다.. 'candies' 만큼의 candy를 얻기위해 평균 몇번의 주사위를 던져야하는지를 구하는 문제..

매우 좋은문제인것 같다.. 오랜만에 제대로 된 DP문제가 나왔는데.. 이상한 sorting문제만 풀고 정작 풀어야할 문제를 못풀어서 아쉽다.. 많은 사람들이 푼 문제인데.. ㅠ_ㅠ;

다음과 같은 점화식을 만들 수 있다..
dp[i] = sum(dp[i-j]) * 1.0 / 6.0 {1 <= j <= 6}

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 double dp[1000001];
      9
     10 class TheDiceGame {
     11 public:
     12
     13 double expectedThrows(int candies)
     14 {
     15     int i, j;
     16     double p = 1.0 / 6.0;
     17     for (i = 1; i <= candies; i++) {
     18         dp[i] = 1.0;
     19         for (j = 1; j <= 6; j++) {
     20             if (i-j > 0)
     21                 dp[i] += dp[i-j] * p;
     22         }
     23     }
     24     return dp[candies];
     25 }
     26
     27 };





[1000] TheNumbersLord

자연수가 들어있는 list와 n이 주어지고.. 이 list에 있는 수를 무조건 한번씩은 다 이용하여 n개의 수를 뽑아서 붙였을때 만들수있는 가장 큰 수를 구하기.. n은 list에 들어있는 수의 개수보다 크거나 같다..

이문제는 사실 UVa-10905 문제와 같다.. -_-; 저 문제를 미리 풀어본 나는 매우 쉽게 풀 수 있었다..;; 또한 이 문제가 엄청나게 tricy하다는 사실도 알고있기때문에.. (uva에서 오답률이 장난아니다..) submit한 사람들도 다 틀릴것이라고 생각하고.. 블챌을 시도했는데 적중했다.. ㅎㅎ

UVa문제와 다른점은 n이 list size보다 클 수 있는데.. 그 경우 모자른만큼을 한가지 수로 채우면 된다.. 그 수는 list에 있는 수 중 가장 자릿수가 높은 수.. tie breaker로 더 큰수를 고르면 된다.. (그냥 젤 큰수로 채우면 될거같군..)


코드는 생략..

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

TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 384 Div2 (완료)  (2) 2007.12.20
TopCoder SRM 383 Div 2 (완료)  (0) 2007.12.14
TopCoder SRM382 DIV2  (2) 2007.12.13
TopCoder SRM381 DIV2 (완료)  (2) 2007.12.09
TopCoder SRM380 DIV2 (완료)  (0) 2007.12.08
TopCoder SRM 379 Div2 (완료)  (0) 2007.11.29
TopCoder SRM378 DIV2 (완료)  (0) 2007.11.21
TopCoder SRM375 DIV2 (Complete)  (6) 2007.11.11
TopCoder SRM374 DIV2  (3) 2007.11.07

Comments

  1. 김우현 2007.12.09 19:01 Permalink Modify/Delete Reply

    멋지세요!

    저는 1000점 tricy에 당한 1인입니다. ㅠ_ㅠ;

    • helloneo 2007.12.09 23:23 신고 Permalink Modify/Delete

      사실 저도 엄청난 삽질끝에 푼 문제랍니다.. ^^;
      우야꼬님도 상승세이시네요.. 다음엔 블루에 도전해보아요.. ^^

Leave a Comment


to Top