TopCoder SRM381 DIV2 (완료)

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

방 1등 전체 8등

방 1등.. 얼마만인가..

rating을 150 이상 올렸다.. 역대 최고의 상승폭..




[250] TheBestName

Problem Statement
     
As some of you may know, there is no name better than JOHN. Let's define the rules for comparing names. Each letter has a weight ('A' - 1, 'B' - 2, ..., 'Z' - 26). The weight of a name is the sum of the weights of all its letters. For example, the name MARK has weight 13 + 1 + 18 + 11 = 43.
When comparing two names, the one with the larger weight is considered better. In case of a tie, the one that comes earlier lexicographically is better. But there is one exception - the name JOHN is the best name of all.
You are given a vector <string> names, each element of which contains a single name. Sort the names from best to worst and return the sorted vector <string>.
Definition
   
Class:
TheBestName
Method:
sort
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> sort(vector <string> names)
(be sure your method is public)
   
 
Constraints
-
names will contain between 1 and 50 elements, inclusive.
-
Each element of names will contain between 1 and 50 characters, inclusive.
-
Each element of names will contain only uppercase letters ('A'-'Z').
Examples
0)
 
   
{"JOHN", "PETR", "ACRUSH"}
Returns: {"JOHN", "ACRUSH", "PETR" }
PETR has weight 59, ACRUSH has weight 70 and JOHN has a weight of only 47. But nevertheless JOHN is the best name, ACRUSH takes second place and PETR is the last.
1)
 
   
{"GLUK", "MARGARITKA"}
Returns: {"MARGARITKA", "GLUK" }
MARGARITKA is definitely better than GLUK.
2)
 
   
{"JOHN", "A", "AA", "AAA", "JOHN", "B", "BB", "BBB", "JOHN", "C", "CC", "CCC", "JOHN"}
Returns:
{"JOHN",
 "JOHN",
 "JOHN",
 "JOHN",
 "CCC",
 "BBB",
 "CC",
 "BB",
 "AAA",
 "C",
 "AA",
 "B",
 "A" }
AA and B both have the same weight, but AA is better as it comes earlier lexicographically. For the same reason, AAA is better than C and BBB is better than CC.
3)
 
   
{"BATMAN", "SUPERMAN", "SPIDERMAN", "TERMINATOR"}
Returns: {"TERMINATOR", "SUPERMAN", "SPIDERMAN", "BATMAN" }
Here are some superheroes sorted by their names.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

단순히 이름을 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

Problem Statement
     
Little John has one standard die with numbers one to six on its sides. Each time he throws the die, he gets as many candies from his mom as the number on the top of the die. John’s goal is to collect at least candies candies. Then he will eat them all and became a little fat boy.
Return the expected number of throws needed for John to achieve his goal.
Definition
   
Class:
TheDiceGame
Method:
expectedThrows
Parameters:
int
Returns:
double
Method signature:
double expectedThrows(int candies)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
candies will be between 1 and 1000000, inclusive.
Examples
0)
 
   
1
Returns: 1.0
John needs only one throw to get at least one candy.
1)
 
   
2
Returns: 1.1666666666666667
After the first throw, there is a probability of 1/6 that John will need an additional throw.
2)
 
   
7
Returns: 2.5216263717421126
 
3)
 
   
47
Returns: 13.90476189046144
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

주사위를 던져서 나온 수 만큼 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

Problem Statement
     
Recently, John had a dream where he was a lord in a world of positive integers. As with all lords, he had to solve a very difficult problem.
John has a list of positive integers. He must pick exactly n integers using this list and concatenate them in any order to produce the largest possible number. The same integer in the list can be chosen multiple times, but each integer must be chosen at least once.
You are given a vector <int> numbers and an int n. Return the largest possible integer that John can create as a string.
Definition
   
Class:
TheNumbersLord
Method:
create
Parameters:
vector <int>, int
Returns:
string
Method signature:
string create(vector <int> numbers, int n)
(be sure your method is public)
   
 
Notes
-
numbers may contain duplicate values. In this case, each integer must be chosen at least as many times as the number of its occurrences in numbers.
Constraints
-
numbers will contain between 1 and 50 elements, inclusive.
-
Each element of numbers will be between 1 and 1,000,000,000, inclusive.
-
n will be between the number of elements in numbers and 50, inclusive.
Examples
0)
 
   
{3,2,7}
3
Returns: "732"
Clearly, it is impossible to get a number greater than 732.
1)
 
   
{4, 7}
4
Returns: "7774"
 
2)
 
   
{1, 10, 100}
4
Returns: "110100100"
To get the largest possible number, John must use 100 twice.
3)
 
   
{4,4,4,4}
9
Returns: "444444444"
Here there is no choice for John at all.
4)
 
   
{1,1,2}
3
Returns: "211"
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

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

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

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


코드는 생략..