어제 저녁 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 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

to Top