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

사용자 삽입 이미지
연속 두번 방 꼴찌.. ㅠ_ㅠ


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

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

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

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


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

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

TopCoder SRM374 DIV2  (3) 2007.11.07
TopCoder SRM 373 Div 2  (0) 2007.10.24
TopCoder SRM 372 Div 2  (8) 2007.10.18
TopCoder SRM 371 Div2 (완료)  (2) 2007.10.14
TopCoder SRM 370 Div2  (0) 2007.10.14
TopCoder SRM369 DIV2  (6) 2007.10.05
TopCoder SRM 368 Div 1  (0) 2007.10.03
TopCoder SRM 367 Div 2 (완료)  (10) 2007.09.27
TopCoder SRM 366 DIV 1  (2) 2007.09.18
TopCoder SRM 365 Div 1  (0) 2007.09.13
TopCoder SRM 364 Div 1  (0) 2007.09.09

Comments

  1. philosup 2007.10.05 16:02 Permalink Modify/Delete Reply

    문제를 제대로 이해했는지 모르겠지만 서도..... 500짜리
    (countA-1)/maxA + 1 ~ countA까지 A문자를 쪼개놓을 수 있는 범위이다.
    이 범위가 중복되는 수가 있거나 1차이가 난다면 모든 문자를 사용할 수 있다.
    중복되는 경우 가 없다면 rangeMinA < rangeMaxA < rangeMinB < rangeMaxB 대략 이런 경우..
    countA + maxB*(countA+1)이 답이 된다.
    업무중에 잠시 생각한것이니 틀렸으면 알려주기 바람 ㅋ

    • helloneo 2007.10.05 17:31 신고 Permalink Modify/Delete

      음.. 이해하기가 힘드네요.. -_-;; 제가 루프를 돌면서 구한걸 한방에 식으로 구하는거 같기는한데..;;;;

  2. philosup 2007.10.05 18:35 Permalink Modify/Delete Reply

    일끝나고 심심해서 방에 들어가서 해봤더니 맞더라~
    설명한참쓰다가 코드가 빠르다-_-;;;
    if(maxA==0 || maxB == 0) return 0;
    rangeMinA = (countA-1)/maxA + 1
    rangeMinB = (countB-1)/maxB + 1
    if(countA +1 < rangeMinB) result = countA + maxB*(countA+1)
    else if(countB +1 < rangeMinA) result = countB + maxA*(countB+1)
    else result = countA + countB;

  3. philosup 2007.10.07 11:17 Permalink Modify/Delete Reply

    니 소스 보니까 예외 처리가 좀 틀렸네;; 내꺼 내가 첼해버렸다 ㅋ
    if(maxA==0 || maxB == 0) return 0;
    이부분이 틀렸네 살작 고치고 추가해야되는디 ㅋ
    if(maxA==0 && maxB == 0) return 0;
    if(maxA==0) return min(countB, maxB);
    if(maxB == 0) return min(countA, maxB);

Leave a Comment


to Top