저녁 9시에 열린 상금매치였다.. 이전 매치에서 삽질하는바람에 div2로 강등됐는데.. 바로 상금매치라니.. 오히려 나한텐 잘된일이었다..;; 이번 셋은 easy는 너무너무 쉽고.. med가 상당히 tricky했다.. 흠.. 그래도 med는 풀줄알았는데.. 끝내 submit을 못했다.. ㅠ_ㅠ;; 아.. 나의 코딩실력이 이거밖에 안되다니.. ㅠ_ㅠ med 문제의 경우 sample이 test case를 제대로 커버하지 못해서 챌린지의 향연이었다.. 결국 챌 덕분에 방 1등 차지.. 음.. 정말 쑥쓰럽군..;;

방 1등 전체 43등..

사용자 삽입 이미지
한문제풀고 1등이라니.. 완전 막장이군.. 빨리 실력을 쌓아야겠다..;; 그래도 다시 div1로 복귀.. 이거 당분간 div1과 div2를 왔다리갔다리 할것같다..



[250] AverageCandyLifetime

more..

모든 캔디가 1월1일에 주어지고.. 매달 말일에 캔디를 먹는다.. 각 달마다 먹은 캔디의 개수가 주어질때 캔디의 평균 생명주기를 구하는 문제..

단순히.. 캔디가 먹히기전까지 기간의 합을 모든 캔디의 수로 나누면 된다..

음.. 코드는 별로 깔끔하지 못하군.. 이정도문제는 240점은 넘겨야하는데.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class AverageCandyLifetime {
  9 public:
 10
 11 double getAverage(vector <int> eatenCandies)
 12 {
 13     int sum[15];
 14     int a, b, i;
 15     sum[1] = 31;
 16     sum[2] = 31+28;
 17     sum[3] = sum[2]+31;
 18     sum[4] = sum[3]+30;
 19     sum[5] = sum[4]+31;
 20     sum[6] = sum[5]+30;
 21     sum[7] = sum[6]+31;
 22     sum[8] = sum[7]+31;
 23     sum[9] = sum[8]+30;
 24     sum[10] = sum[9]+31;
 25     sum[11] = sum[10]+30;
 26     sum[12] = sum[11]+31;
 27     a = b = 0;
 28     for (i = 0; i < eatenCandies.size(); i++) {
 29         a += eatenCandies[i] * sum[i+1];
 30         b += eatenCandies[i];
 31     }
 32     return (double)a / (double)b;
 33 }
 34
 35 };




[500] TwoStringMasks

more..

두개의 문자열이 주어지고 각각의 문자열은 중간에 하나의 '*' 이 있다.. 이 '*'은 임의의 문자열로 대치될 수 있을때 두 문자열을 같게 만드는 최소의 문자열 찾기.. 불가능하면 "impossible" return..

음.. 그냥 단순히 코딩하면 되는데.. 결국 실패.. ㅠ_ㅠ 막판에 sample 하나가 안나와서 수정하다가 결국 submit을 못했다..

문제풀다가 생각해 낸 tricky case는 {"ABC*ABC", "*BC"} 였는데.. 역시나.. submit한 6명중에 4명이나 fail했다.. ㅎㅎㅎ 나머지 두명도 system test때 다 fail하고.. 결국.. 얼떨결에 1등을 해버렸군..

아.. 쉽지않은 문제였다.. ㅠ_ㅠ;; 열라 삽질코딩끝에.. 겨우 pass..!!

우선 왼쪽 같은부분 제거.. 그다음 오른쪽 같은부분 제거..
이제 *을 사이에두고 남은 왼쪽과 오른쪽 string이 둘다 하나의 string에서 온것이라면 특별처리..
그게 아니라 하나는 첫번째 하나는 두번째 string에서 왔다면.. 겹치는부분을 제거하면서 붙인다..

휴.. 코딩이 완전 엉망이네.. ㅠ_ㅠ;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 void rev(char* x)
  9 {
 10     char temp[100];
 11     int i, j, len;
 12     len = strlen(x);
 13     for (i = 0, j = len-1; i < len; i++, j--) {
 14         temp[i] = x[j];
 15     }
 16     temp[i] = 0;
 17     strcpy(x, temp);
 18 }
 19
 20 void make_str(char* ss1, char* ss2, char* buf)
 21 {
 22     int i, j, k;
 23     int len1, len2;
 24     len1 = strlen(ss1);
 25     len2 = strlen(ss2);
 26     if (len1 == 0 && len2 == 0) {
 27         buf[0] =0;
 28         return ;
 29     }
 30     if (len1 == 0) {
 31         strcpy(buf, ss2);
 32         return ;
 33     }
 34     if (len2 == 0) {
 35         strcpy(buf, ss1);
 36         return ;
 37     }
 38
 39     for (i = 0; i < len1; i++) {
 40         if (i + len2 < len1)
 41             continue;
 42         for (k = 0; k < len2; k++) {
 43             if (k+i < len1 && ss1[k+i] != ss2[k])
 44                 break;
 45         }
 46         if (k == len2)
 47             break;
 48     }
 49     strcpy(buf, ss1);
 50     for (j = i, k = 0; k < len2; k++, j++) {
 51         buf[j] = ss2[k];
 52     }
 53     buf[j] = 0;
 54 }
 55
 56 class TwoStringMasks {
 57 public:
 58
 59 string shortestCommon(string s1, string s2)
 60 {
 61     char str1[100], str2[100];
 62     char temp1[100], temp2[100], buf[100];
 63     char f[100], e[100];
 64     int a1, a2, b1, b2;
 65     int len1, len2;
 66     int i, j, k;
 67     string xx, yy, zz, res;
 68     strcpy(str1, s1.c_str());
 69     strcpy(str2, s2.c_str());
 70     len1 = strlen(str1);
 71     len2 = strlen(str2);
 72     if (!strcmp(str1, "*") && !strcmp(str2, "*"))
 73         return "";
 74
 75     for (i = 0; i < len1 && i < len2; i++) {
 76         if (str1[i] == '*' || str2[i] == '*')
 77             break;
 78         f[i] = str1[i];
 79         if (str1[i] != str2[i])
 80             return "impossible";
 81     }
 82     f[i] = 0;
 83     a1 = i;
 84     b1 = i;
 85
 86     for (i = len1-1, j = len2-1, k = 0; i >= 0 && j >= 0; i--, j--, k++) {
 87         if (str1[i] == '*' || str2[j] == '*')
 88             break;
 89         e[k] = str1[i];
 90         if (str1[i] != str2[j])
 91             return "impossible";
 92     }
 93     e[k] = 0;
 94     rev(e);
 95     a2 = i;
 96     b2 = j;
 97
 98     if (str2[b1] == '*') {
 99         if (str1[a2] == '*') {
100             for (i = a1, j = 0; i < len1; i++, j++) {
101                 if (str1[i] == '*') {
102                     temp1[j] = 0;
103                     break;
104                 }
105                 temp1[j] = str1[i];
106             }
107             for (i = 0; i < len2; i++) {
108                 if (str2[i] == '*')
109                     break;
110             }
111             i++;
112             for (j = 0; i <= b2; i++, j++) {
113                 temp2[j] = str2[i];
114             }
115             temp2[j] = 0;
116             make_str(temp1, temp2, buf);
117 printf("temp1 = %s, temp2 = %s, buf = %s\n", temp1, temp2, buf);
118         }
119         else {
120             for (i = 0, j = 0; i < len1; i++) {
121                 if (str1[i] == '*')
122                     continue;
123                 buf[j++] = str1[i];
124             }
125             buf[j] = 0;
126             res = buf;
127             return res;
128         }
129     }
130     else if (str1[a1] == '*') {
131         if (str2[b2] == '*') {
132             for (i = b1, j = 0; i < len2; i++, j++) {
133                 if (str2[i] == '*') {
134                     temp1[j] = 0;
135                     break;
136                 }
137                 temp1[j] = str2[i];
138             }
139             for (i = 0; i < len1; i++) {
140                 if (str1[i] == '*')
141                     break;
142             }
143             i++;
144             for (j = 0; i <= a2 ; i++, j++) {
145                 temp2[j] = str1[i];
146             }
147             temp2[j] = 0;
148             make_str(temp1, temp2, buf);
149 printf("temp1 = %s, temp2 = %s, buf = %s\n", temp1, temp2, buf);
150         }
151         else {
152             for (i = 0, j = 0; i < len2; i++) {
153                 if (str2[i] == '*')
154                     continue;
155                 buf[j++] = str2[i];
156             }
157             buf[j] = 0;
158             res = buf;
159             return res;
160         }
161     }
162 printf("f = %s, buf = %s\n", f, buf);
163     xx = f;
164     yy = buf;
165     zz = e;
166     res = xx+yy+zz;
167 printf("res ------------> %s\n", res.c_str());
168     return res;
169 }
170
171 };




[1000] QuasiLatinSquares

more..



to be updated..

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

TopCoder SRM 398 Div1  (0) 2008.04.16
TopCoder SRM 397 Div2 (완료)  (0) 2008.04.13
SRM 395 Div1  (0) 2008.04.09
TopCoder SRM 394 Div 1  (2) 2008.03.24
흠냥.. 탑코더 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
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03

Leave a Comment


to Top