TopCoder SRM369 DIV2

흠.. 이번 SRM을 통해서 나의 실력의 부족함을 여러모로 많이 느꼈다.. 연속 두번 꼴찌.. 헐..;;
이번엔 500점짜리를 악전고투끝에 풀긴 했지만.. 챌린지를 잘못해서 딴 점수를 다 날려버렸다.. ㅠ_ㅠ
챌린지를 잘할수있도록 집중연습해야겠다.. 남들은 챌 잘만하던데.. 젠장!
초반에 되지도않는 1000점짜리 문제가지고 삽질하다고 시간좀 허비하고 500점짜리 힘겹게 풀었다.. 마지막에 250점짜리를 열었는데.. 역시 별로 어렵지는 않았지만.. 시간도 촉박하고 해서 그냥 접었다..

연속 두번 방 꼴찌.. ㅠ_ㅠ


[250] ChainOfRectangles

Problem Statement
    
A sequence of rectangles is drawn on a plane that is initially completely white. Each rectangle lies strictly inside the previous one. Each rectangle is completely colored in one of three colors - red, green or blue. The colors do not mix, so when a rectangle is drawn inside another rectangle, the new color replaces any existing color in that same area.
The rectangles are described by the vector <int>s width and height, and the string color. The width and height of the i-th drawn rectangle are width[i] and height[i], respectively, and its color is the i-th character of color. The characters 'R', 'G' and 'B' represent red, green and blue, respectively.
After all the rectangles are drawn, calculate the total area occupied by red, the total area occupied by green, and the total area occupied by blue. Return the maximum of these three areas.
Definition
   
Class:
ChainOfRectangles
Method:
getMaximalArea
Parameters:
vector <int>, vector <int>, string
Returns:
int
Method signature:
int getMaximalArea(vector <int> width, vector <int> height, string color)
(be sure your method is public)
   
 
Notes
-
You won't be given the information about the exact location of each rectangle, since it's not needed to solve the problem.
Constraints
-
width will contain between 1 and 50 elements, inclusive.
-
height will contain the same number of elements as width.
-
color will contain the same number of characters as the number of elements in width.
-
Each element of width and height will be between 1 and 10000, inclusive.
-
Elements of width and height will be in strictly descending order.
-
Each character of color will be 'R', 'G' or 'B'.
Examples
0)
 
   
{10000}
{10000}
"R"
Returns: 100000000
There is only one 10,000x10,000 rectangle. It's colored red, so the area covered by red is 10,000 * 10,000 = 100,000,000. The areas covered by the other two colors are 0.
1)
 
   
{10, 5}
{10, 5}
"GB"
Returns: 75
Here, the area covered by blue is 5 * 5 = 25 and the area, covered by green is 10 * 10 - 5 * 5 = 75. We return max{75, 25} = 75.

 
2)
 
   
{10, 9}
{8, 7}
"GB"
Returns: 63
Now, the area covered by green is 17, and the area covered by blue is 63.
 
3)
 
   
{10, 8, 6, 4, 2}
{9, 7, 5, 3, 1}
"GBRRG"
Returns: 36
 
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.

여러개의 사각형이 중첩되어서 놓여있고 각각의 색깔이 주어진다.. 이때 가장 넓이가 큰 색깔의 넓이 구하기..

별다른 알고리즘이 없다.. 그냥 시키는대로 구현하면 되는문제.. 이문제를 괜히 챌 시도했다가 점수깎였다.. 이문제는 거의 틀리는 사람이 없었다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7 #define max(x, y) ((x) > (y) ? (x) : (y))
      8
      9 class ChainOfRectangles {
     10 public:
     11
     12 int getMaximalArea(vector<int> width, vector<int> height, string color)
     13 {
     14     int i, temp, n;
     15     int w[100], h[100];
     16     int r, g, b;
     17     char buf[100];
     18     char ch;
     19
     20     n = width.size();
     21     strcpy(buf, color.c_str());
     22     for (i = 0; i < n; i++) {
     23         w[i] = width[i];
     24         h[i] = height[i];
     25     }
     26     r = g = b = 0;
     27     if (buf[0] == 'R')
     28         r = w[0] * h[0];
     29     else if (buf[0] == 'G')
     30         g = w[0] * h[0];
     31     else
     32         b = w[0] * h[0];
     33     for (i = 1; i < n; i++) {
     34         temp = w[i] * h[i];
     35         ch = buf[i];
     36         if (ch == 'R') {
     37             if (buf[i-1] == 'R')
     38                 r -= temp;
     39             else if (buf[i-1] == 'G')
     40                 g -= temp;
     41             else
     42                 b -= temp;
     43             r += temp;
     44         }
     45         else if (ch == 'G') {
     46             if (buf[i-1] == 'R')
     47                 r -= temp;
     48             else if (buf[i-1] == 'G')
     49                 g -= temp;
     50             else
     51                 b -= temp;
     52             g += temp;
     53         }
     54         else {
     55             if (buf[i-1] == 'R')
     56                 r -= temp;
     57             else if (buf[i-1] == 'G')
     58                 g -= temp;
     59             else
     60                 b -= temp;
     61             b += temp;
     62         }
     63     }
     64     return max(r, max(g, b));
     65 }
     66
     67 };

[500] BeautifulString

Problem Statement
    
A string composed of the letters 'A' and 'B' is called beautiful if it satisfies all of the following criteria:
it contains no more than countA occurences of 'A';
it contains no more than countB occurences of 'B';
each substring that contains only 'A's consists of no more than maxA characters;
each substring that contains only 'B's consists of no more than maxB characters.
Given countA, countB, maxA and maxB, return the maximum possible length of a beautiful string.
Definition
   
Class:
BeautifulString
Method:
maximumLength
Parameters:
int, int, int, int
Returns:
int
Method signature:
int maximumLength(int countA, int countB, int maxA, int maxB)
(be sure your method is public)
   
 
Constraints
-
countA will be between 0 and 1000000, inclusive.
-
countB will be between 0 and 1000000, inclusive.
-
maxA will be between 0 and 1000000, inclusive.
-
maxB will be between 0 and 1000000, inclusive.
Examples
0)
 
   
0
0
10
10
Returns: 0
We don't have any available letters as countA=0 and countB=0, so the only beautiful string is the empty one.
1)
 
   
10
10
0
0
Returns: 0
Now we have available letters, but can't include them into the beautiful string as maxA=0 and maxB=0.
2)
 
   
3
5
1
1
Returns: 7
In this case we can't have two consecutive 'A's or 'B's, so letters in the beautiful string should alternate. If we start the string from 'A', the longest one we'll be able to get is "ABABAB". But if we start the string from 'B', we'll be able to get the longer one - "BABABAB".
3)
 
   
677578
502524
989951
504698
Returns: 1180102
Here maxA >= countA and maxB >= countB, so we can easily construct a beautiful string using all available countA+countB letters.
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.

countA는 'A' 문자의 최대 개수, countB는 'B' 문자의 최대 개수, maxA는 'A'로만 이루어진 substring중 만들수있는 최대 길이, maxB는 'B'로만 이루어진 substring중 만들수 있는 최대 길이.. 이때 'A'와 'B'로 이루어진 만들수있는 최대길이의 string을 구하는 문제..

상당히 괜찮은 문제인거같다.. 나름 고민도 하고 세번의 resubmit끝에 힘겹게 풀어냈다..
우선 max값 또는 count값이 0인경우 특별처리해준다.. 그 이외의 경우는 하나씩 번갈아가면서 놓는것을 원칙으로 하고 그래도 남는 경우는 max값을 넘지 않는 범위에서 각각의 slot(?)에 한개씩 더 끼워넣는짓을 반복한다..


예)
1) countA와 countB가 같은경우..
ABABAB..AB -> 선택의 여지가 없다..

2) countA가 countB보다 클경우..
ABABAB...A  -> 이런 식으로 놓아야 최대가 된다..

그래도 A의 개수가 남을경우..
AABAABAAB...BAA
AAABAAABAAAB...BAAA
이런식으로 maxA의 값을 넘지 않고 A가 다 떨어지기 전까지 A를 늘려나간다..

      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
     10 class BeautifulString {
     11 public:
     12
     13 int maximumLength(int countA, int countB, int maxA, int maxB)
     14 {
     15     int res, left;
     16     int temp1, temp2, temp3;
     17     int i, k;
     18     res = countA + countB;
     19     if (maxA >= countA && maxB >= countB)
     20         return res;
     21     if (maxB == 0)
     22         return min(countA, maxA);
     23     if (maxA == 0)
     24         return min(countB, maxB);
     25     if (countA == 0)
     26         return min(countB, maxB);
     27     if (countB == 0)
     28         return min(countA, maxA);
     29
     30     if (countA == countB) {
     31         return countA+countB;
     32     }
     33     if (countB > countA) {
     34         temp1 = countA;
     35         countA = countB;
     36         countB = temp1;
     37         temp1 = maxA;
     38         maxA = maxB;
     39         maxB = temp1;
     40     }
     41     res = countB * 2;
     42     left = countA - countB;
     43 printf("res = %d, left = %d\n", res, left);
     44     res++;
     45     left--;
     46 printf("res = %d, left = %d\n", res, left);
     47     if (left) {
     48         k = countB+1;
     49         temp1 = res;
     50         temp3 = left;
     51         for (i = 1; i < maxA && temp3 > 0; i++) {
     52             if (temp3 >= k) {
     53                 temp3 -= k;
     54                 temp1 += k;
     55             }
     56             else {
     57                 temp1 += temp3;
     58                 temp3 = 0;
     59             }
     60         }
     61         temp3 = left;
     62         temp2 = res;
     63         for (i = 1; i < maxB && temp3 > 0; i++) {
     64             if (temp3 >= k-1) {
     65                 temp3 -= k-1;
     66                 temp2 += k-1;
     67             }
     68             else {
     69                 temp3 = 0;
     70                 temp2 += k-1;
     71             }
     72         }
     73 printf("temp1 = %d, temp2 = %d\n", temp1, temp2);
     74         res = max(temp1, temp2);
     75         return temp1;
     76     }
     77     return res;
     78 }
     79
     80 };

자세히 보면 좀 필요없는 코드들이 있다.. -_-;; 코딩하면서 상당히 고민한 흔적을 볼수있다.. ㅋㅋㅋ




[1000] IsoscelesTriangulations

Problem Statement
    
Let's consider a regular polygon on the plane with n vertices, numbered from 0 to n-1, inclusive. The polygon's n-3 diagonals are called a triangulation if no two diagonals intersect at a point strictly inside the polygon. Two triangulations A and B are considered to be distinct if there are two vertices i and j such that A contains the diagonal between vertices i and j, and B doesn't contain this diagonal.
It's not hard to see that every triangulation breaks the polygon into n-2 triangles. The triangulation is called k-isosceles, if there are exactly k isosceles triangles among them. Given ints n and k, compute the number of distinct k-isosceles triangulations of a regular polygon with n vertices. Return the result modulo 123456789.
Definition
   
Class:
IsoscelesTriangulations
Method:
getCount
Parameters:
int, int
Returns:
int
Method signature:
int getCount(int n, int k)
(be sure your method is public)
   
 
Notes
-
A triangle is called isosceles if it has at least 2 sides with equal length.
-
A regular polygon is a polygon which is equiangular (all angles are congruent) and equilateral (all sides have the same length).
-
A diagonal is a line joining two nonadjacent vertices of a polygon.
Constraints
-
n will be between 3 and 50, inclusive.
-
k will be between 0 and n-2, inclusive.
Examples
0)
 
   
4
2
Returns: 2
We can have a diagonal between vertices 0 and 2 or between vertices 1 and 3. In both cases, there are 2 isosceles triangles.
1)
 
   
3
0
Returns: 0
The only triangulation of an equilateral triangle contains no diagonals and 1 isosceles triangle (the polygon itself).
2)
 
   
5
3
Returns: 5
A regular pentagon has 5 triangulations. Each of them is obtained by connecting one selected vertex with the two others that are not its neighbors, so each triangulation is 3-isosceles.
3)
 
   
6
2
Returns: 12
All 2-isosceles triangles of a regular hexagon are shown in the picture below. All isosceles triangles in each triangulation are colored purple.
 
4)
 
   
10
8
Returns: 10
All 8-isosceles triangulations of a regular 10-gon are shown in the picture below. All triangles in each triangulation are isosceles.
 
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.

정 n각형을 triangulation하는데 단 k개의 이등변 삼각형만 나와야한다.. 이렇게 triangulation할 수 있는 방법의 개수를 구하는 문제..

역시..쉽지않은 문제이다.. -_-


이번 SRM도 system 문제로 rating에 영향을 주지 않았다.. 오히려 나한테는 더 좋지않은 결과이다.. ㅠ_ㅠ