어제 저녁 8시에 열린 매치..
그동안의 부진을 좀 만회하고자 이번에는 좀 정신차리고 했는데.. 또 망쳐버렸다.. ㅠ_ㅠ
250이 열라 코딩이 드러운 문제가 나오면서.. 또 험난한 매치가 되어버렸다..
단순한 코딩 실수를 못찾아서 한참 헤맨게 컸다.. 젠장..
500은 다들 똑같은 DP로 풀었고.. 250은 코드가 다들 개발새발이라 도저히 챌을 할 수가 없었다..

결국 20점 하락 ㅠ_ㅠ;;;;
겨우 삽질해서 한문제 풀었더니.. 이거 허무하구만..




Level1 - T9

전화 키패드를 이용해서 문자를 보낸다고 생각하면 되는데.. 각 번호마다 타이핑할 수 있는 알파벳이 있다..
숫자로 뭐라고뭐라고 쳤을때 나오는 결과가 무었일지..
0은 빈칸을 의미하고, # 은 가능한 단어중에 다음거 선택, * 은 가능한 단어중에 5번째꺼 선택 을 의미..

그냥 brute force 로 다 찾으면 된다..
코딩을 거의 잘 해놓고도.. 단순 실수를 못찾아서 헤맸다..

나같은 경우, 일단 dictionary 에 있는 단어들을 encoding 해놓았다..
input 을 parsing 해서 그걸 앞에서 encoding 해둔 map 을 이용해서 계속 찾아나갔다..

아래는 내가 매치중에 짠 코드인데.. 이건 뭐 완전..  -_-;;;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 #include <set>
  8 using namespace std;
  9 //#define min(x, y) ((x) > (y) ? (y) : (x))
 10 //#define max(x, y) ((x) > (y) ? (x) : (y))
 11 //#define INF 999999999
 12 //#define EPS 1e-14
 13
 14 string pp[128];
 15 set<string> dd;
 16 set<string> ss;
 17 map<string, set<string> > ms;
 18
 19 string find_str(string in, int n)
 20 {
 21     int i;
 22     set<string> temp_set;
 23     set<string>::iterator it;
 24
 25     if (in.size() == 0)
 26         return "";
 27     temp_set = ms[in];
 28
 29     n = n % temp_set.size();
 30
 31     for (it = temp_set.begin(), i = 0; it != temp_set.end() && i < n; it++, i++) {
 32     }
 33     return *it;
 34 }
 35
 36 class T9 {
 37 public:
 38
 39 string message(vector <string> part, vector <string> dict, vector <string> keystr)
 40 {
 41     int i, j, k, l;
 42     int len, cnt;
 43     char ch;
 44     string res;
 45     string cur;
 46     string in, temp;
 47     set<string> temp_set;
 48
 49     for (i = 1; i <= 9; i++) {
 50         pp[i] = part[i-1];
 51     }
 52     dd.clear();
 53     for (i = 0; i < dict.size(); i++) {
 54         dd.insert(dict[i]);
 55     }
 56
 57     for (i = 0; i < dict.size(); i++) {
 58         temp = dict[i];
 59         cur = "";
 60         for (j = 0; j < temp.size(); j++) {
 61             for (k = 1; k <= 9; k++) {
 62                 for (l = 0; l < pp[k].size(); l++) {
 63                     if (pp[k][l] == temp[j]) {
 64                         cur += (char)('0' + k);
 65                         break;
 66                     }
 67                 }
 68                 if (l < pp[k].size())
 69                     break;
 70             }
 71         }
 72
 73         //printf("found .. %s\n", cur.c_str());
 74         if (ms.find(cur) == ms.end()) {
 75             temp_set.clear();
 76             temp_set.insert(dict[i]);
 77             ms[cur] = temp_set;
 78         }
 79         else {
 80             temp_set = ms[cur];
 81             temp_set.insert(dict[i]);
 82             ms[cur] = temp_set;
 83         }
 84     }
 85
 86     res = "";
 87     cur = "";
 88     in = "";
 89     for (i = 0; i < keystr.size(); i++) {
 90         in += keystr[i];
 91     }
 92
 93     len = in.size();
 94     for (i = 0; i < len; i++) {
 95         ch = in[i];
 96         if (ch == '*' || ch == '#') {
 97             cnt = 0;
 98             while (i < len && (in[i] == '*' || in[i] == '#')) {
 99                 if (in[i] == '*')
100                     cnt += 5;
101                 else
102                     cnt += 1;
103                 i++;
104             }
105             i--;
106             temp = find_str(cur, cnt);
107             res += temp;
108             cur = "";
109             continue;
110         }
111         else if (in[i] == '0') {
112             temp = find_str(cur, 0);
113             res += temp;
114             res += " ";
115             cur = "";
116             continue;
117         }
118         else {
119             cur += ch;
120         }
121     }
122
123     if (cur.size() != 0) {
124         temp = find_str(cur, 0);
125         res += temp;
126     }
127     return res;
128 }
129
130 };



Level2 - RoadOrFlightHard


to be updated..



Level3 - MallSecurity


to be updated..


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

SRM 472 - 현충일 새벽에 삽질..  (0) 2010.06.07
SRM 470  (0) 2010.05.28
TCO10 Qual3 - 이런 젠장  (0) 2010.05.25
TCO10 Qaul2  (2) 2010.05.13
SRM 469  (0) 2010.05.05
[SRM 468] 보람이 없구만..  (0) 2010.04.21
SRM 466  (0) 2010.04.05
TopCoder Open 2010 일정..  (0) 2010.03.31
SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20

Leave a Comment


to Top