## TopCoder SRM 417 Div 2

목요일 밤 12시에 열린 매치.. 이번에도 꽤 많은 사람이 참여했다.. 거의 1700명이 참여했고.. 한국사람도 40명 넘게 참여했다.. 한국사람중에도 최근에 탑코더를 시작한사람이 많아서.. 생소한 아이디들도 많다.. 흠.. 누가 누군지 모르겠다..
나는 이번에도 div2에서 했는데.. 간신히 두문제 풀고.. 1000점짜리 보다가 문제도 어렵고 너무 피곤해서 도저히 풀 엄두가 나지 않았다.. 결국 노가다문제 두개 풀고 그냥 포기했는데.. 음.. 1000점짜리 해법이 궁금하네..;;
이번에는 챌린지도 하지 못했다.. 250은 틀리는사람이 없을테고.. 500은 코드가 다들 넘 어려워서.. ㅠ_ㅠ 500도 생각보다 많이 맞았다.. 챌 했으면 큰일날뻔했다..
결과는 방 2등 전체 64등.. rating은 68점을 올려서 1196 -_- 아깝게 4점이 모자라서 다음에도 또 div2이다.. 젠장!! div1에서는 그냥 꼴등을 해도 별 부담이 없는데.. 이거 div2가 훨 부담스럽네.. Level1 - ReversedSum

Rev()는 숫자를 거꾸로 뒤집은 연산이다.. (leading zero는 취급 X) 즉, Rev(321) = 123, Rev(100) = 1 이 된다.. input으로 x, y가 주어질때, Rev(Rev(x) + Rev(y)) 구하기

매우 쉬운문제.. 모처럼 240을 넘겼지만.. 그래도 순위에서 한참 밀렸다.. -_-

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 int rev(char* buf)
9 {
10     int len;
11     int i, j;
12     char temp;
13     len = strlen(buf);
14     for (i = 0, j = len-1; i < len; i++, j--) {
15         temp[i] = buf[j];
16     }
17     temp[i] = 0;
18     return atoi(temp);
19 }
20
21 class ReversedSum {
22 public:
23
24 int getReversedSum(int x, int y)
25 {
26     int a, b;
27     char buf, buf2;
28     sprintf(buf, "%d", x);
29     sprintf(buf2, "%d", y);
30     a = rev(buf);
31     b = rev(buf2);
32 printf("a = %d, b = %d\n", a, b);
33     sprintf(buf, "%d", a+b);
34     return rev(buf);
35 }
36
37 };

Level2 - TemplateMatching

input으로 text, prefix, suffix가 주어질때, text의 substring 중에서 앞에 prefix를 중첩시키고, 뒤에 suffix를 중첩시킬때 (당근 같은 letter여야만 중첩이 됨).. 그 중첩된 크기가 score이다. 이 score를 최대화하는 text의 substring 구하기.. 답이 여러개면 prefix가 많이 중첩되는거.. 그것도 여러개면 lexy-smallest를 구한다.

주어진 text에 대해 모든 substring을 다 구하고 각각에 대해 score를 구했다.. 단순 노가다 문제..
음.. 소스가 무지 복잡하군.. ㅠ_ㅠ

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 char pre, suf, t;
9 int len, len1, len2;
10
11 void get_sub(int u, int l, char* sub)
12 {
13     int i, j;
14     for (i = 0, j = u; i < l; i++, j++) {
15         sub[i] = t[j];
16     }
17     sub[i] = 0;
18 }
19
20 int get_score1(char* sub, int len3)
21 {
22     char temp;
23     int i, j, k;
24     int max1, len4;
25     max1 = 0;
26     for (i = 0; i < len1; i++) {
27         strcpy(temp, &pre[i]);
28         if (strlen(temp) > len3)
29             continue;
30         len4 = strlen(temp);
31         for (j = 0, k = 0; j < len4; j++, k++) {
32             if (temp[j] != sub[k])
33                 break;
34         }
35         if (j == len4 && max1 < len4) {
36             max1 = len4;
37         }
38     }
39     return max1;
40 }
41
42 int get_score2(char* sub, int len3)
43 {
44     char temp;
45     int i, j, k;
46     int max1, len4;
47     max1 = 0;
48     for (i = 0; i < len3; i++) {
49         strcpy(temp, &sub[i]);
50         len4 = strlen(temp);
51         if (len4 > len2)
52             continue;
53         for (j = 0, k = 0; j < len4; j++, k++) {
54             if (temp[j] != suf[k])
55                 break;
56         }
57         if (j == len4 && max1 < len4) {
58             max1 = len4;
59         }
60     }
61     return max1;
62 }
63
64 class TemplateMatching {
65 public:
66
67 string bestMatch(string text, string prefix, string suffix)
68 {
69     char sub;
70     int a, b;
71     int i, j;
72     int max1, idx1, idx2;
73     char res;
74     strcpy(pre, prefix.c_str());
75     strcpy(suf, suffix.c_str());
76     strcpy(t, text.c_str());
77     len = strlen(t);
78     len1 = strlen(pre);
79     len2 = strlen(suf);
80     res = 0;
81     max1 = -1;
82     idx1 = idx2 = -1;
83     for (i = 1; i <= len; i++) {
84         for (j = 0; j+i-1 < len; j++) {
85             get_sub(j, i, sub);
86             a = get_score1(sub, i);
87             b = get_score2(sub, i);
88 //printf("sub = %s, a = %d, b = %d\n", sub, a, b);
89             if (max1 < a+b) {
90                 max1 = a+b;
91                 idx1 = a;
92                 idx2 = b;
93                 strcpy(res, sub);
94             }
95             else if (max1 == a+b) {
96                 if (idx1 < a) {
97                     strcpy(res, sub);
98                     idx1 = a;
99                     idx2 = b;
100                 }
101                 else if (idx1 == a) {
102                     if (strcmp(sub, res) < 0) {
103                         strcpy(res, sub);
104                     }
105                 }
106             }
107         }
108 //printf("max1 = %d ----- sub = %s\n", max1, res);
109     }
110 printf("res = %s\n", res);
111     string ret = res;
112     return ret;
113 }
114
115 };

Level3 - TripleJump

to be updated..

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

 TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13 2008.10.19 2008.10.12 2008.10.03 2008.09.21 2008.09.13 2008.09.07 2008.08.17 2008.08.08 2008.08.01 2008.07.20