새벽 1시에 열린 매치.. 완전 안드로메다로 제대로 가버리고 말았다..~ 250점짜리부터 생각보다 빡세서 허우적거리다가.. 결국 어처구니없게 system test에서 fail하고 말았다.. ㅠ_ㅠ 조금만 신경썼으면 충분히 pass할 수 있었는데.. 아쉽군.. 쩝..;; 600점 짜리도 장난아니었고.. 900은 아직 문제도 모름..

Match editorial에 쓰여진 글.. 얼마나 공부해야 페트르처럼 될까..? -_-;;

A healthy turnout of 1500 coders was faced with tough problemsets in both divisions. However, that was no obstacle for Petr to show impressive times on both medium and hard and to win Division 1 achieving the best-ever rating of 3799 (and with such high rating revealing a bug in the rating distribution application, as well :))

방 12등 전체 428등..

사용자 삽입 이미지
완전 제대로 빵점이네.. -_-;; 문제가 어려운 덕분에.. 겨우 2부리그 추락은 막았다..;;;; 600점 이상은 푼사람은 커녕 submit 해본 사람도 없군 이런..;;



[250] RoughStrings
문자열과 integer n 이 주어지고.. 주어진 문자열에서 n개 이하의 문자를 지울 수 있다.. 이때 각 문자별로 남는 최대 개수와 최소 개수의 차를 구하는 문제..

처음에 greedy하게 생각해서 무조건 많은 문자에대해서 지우면 된다고 판단.. 한개씩 지우고 sort하고 다시 지우고 sort하고.. 해보니.. 마지막 case가 답이 나오지 않았다.. OTL.. ㅠ_ㅠ

마지막 케이스:
"bbbccca" => 이때는 a 하나만 지우면 답이 0이 되어서 최소가 된다..

그래서 마땅한 greedy 전략이 생각이 안나서.. backtracking으로 시도.. 적은 수의 문자를 지울때는 그 개수만큼 지우고.. 많은 수의 문자를 지울때는 한개씩 지웠다..

흠.. 맞았다고 생각했는데 결국 time limit으로 fail.. 흑흑.. 설마 time limit이 날까 했는데.. 생각보다 무식한 input이 있었다..;; 근데 time limit으로 fail한 사람이 은근히 많았다..

backtracking전략을 사용하되 pruining 조건을 하나 추가했다.. (적은 수의 문자를 빼다가 일단 많은 수의 문자를 빼기 시작하면 그때부터는 무조건 많은 수의 문자를 뺀다..)

다른사람 코드는 간단하던데.. 내꺼는 왜이렇지.. ㅠ_ㅠ;;;
뭔가 다른 쉬운 방법이 있는것 같다..

  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
  9 int min1;
 10
 11 int comp(const void* x, const void* y)
 12 {
 13     int* a = (int*)x;
 14     int* b = (int*)y;
 15     return *b - *a;
 16 }
 17
 18 void dfs(int n, int* cnt, int fl)
 19 {
 20     int i, j;
 21     int temp_cnt[26];
 22     if (min1 == 0)
 23         return ;
 24     qsort(cnt, 26, sizeof(int), comp);
 25     if (n < 0)
 26         return ;
 27     for (j = 25; j >= 0; j--) {
 28         if (cnt[j] != 0)
 29             break;
 30     }
 31     if (j < 0) {
 32         min1 = 0;
 33         return ;
 34     }
 35     min1 = min(min1, cnt[0]-cnt[j]);
 36
 37 //printf("cnt[0] = %d, cnt[%d] = %d\n", cnt[0], j, cnt[j]);
 38
 39     if (n <= 0)
 40         return ;
 41     for (i = 0; i < 26; i++) {
 42         temp_cnt[i] = cnt[i];
 43     }
 44     if (temp_cnt[j] <= n && fl == 0) {
 45         temp_cnt[j] = 0;
 46         dfs(n-cnt[j], temp_cnt, 0);
 47     }
 48     temp_cnt[j] = cnt[j];
 49     temp_cnt[0]--;
 50     dfs(n-1, temp_cnt, 1);
 51 }
 52
 53 class RoughStrings {
 54 public:
 55
 56 int minRoughness(string s, int n)
 57 {
 58     int cnt[26];
 59     int i, j, len;
 60     int a, b;
 61     char buf[100];
 62     strcpy(buf, s.c_str());
 63     len = strlen(buf);
 64     memset(cnt, 0, sizeof(cnt));
 65     for (i = 0; i < len; i++) {
 66         cnt[buf[i] - 'a']++;
 67     }
 68     qsort(cnt, 26, sizeof(int), comp);
 69     a = cnt[0];
 70     for (j = 25; j >= 0; j--) {
 71         if (cnt[j] != 0)
 72             break;
 73     }
 74     b = cnt[j];
 75     min1 = a - b;
 76     dfs(n, cnt, 0);
 77     printf("min1 = %d\n", min1);
 78     return min1;
 79 }
 80
 81 };




[600] CentersOfSymmetry



to be updated..




[900] PseudoRandomKingdom



to be updated..


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

리눅스에서 탑코더하기..  (0) 2008.05.01
TopCoder SRM 399 Div 1  (0) 2008.04.25
TopCoder SRM 398 Div1  (0) 2008.04.16
TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
SRM 395 Div1  (0) 2008.04.09
흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27
TopCoder TCO08 Online Round 1  (2) 2008.02.17
TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15

to Top