쓰러졌음 ' ㅅ'

안녕하세요. Astein 입니다.

회사에 아침 8시에 출근해서 GCJ Qual을 했는데, 세팅이 제대로 안되서... ㅜㅜ

12등이라는 성적을 거두긴 했는데, 10등 안에 못들어서 아쉽네요 :(

-------------------------------------------------------------------------

A. Alien Language

  외계어는 L개의 소문자로 이루어진 단어 D개가 있다. N개의 패턴이 주어졌을 때, 각각의 패턴에 해당하는 단어가 몇개씩
있는지 구하는 프로그램을 작성하시오. 패턴의 각 글자는 소문자거나 괄호로 둘러쌓여진 소문자들의 그룹으로 이루어져 있다. 예를 들어 (ab)d(dc) 같은 경우, 첫 글자는 a 또는 b, 두번째 글자는 d, 세번째 글자는 d 또는 c인 단어를 의미하며, add, adc, bdd, bdc 의 4가지 가능성이 있다.

B. Watersheds

  높이가 표시된 지도가 있다. 어떤 위치에 비가 오는 경우, 빗물은 특정한 조건에 따라 흐른다.

  1. 각 칸에서 빗물은 인접한 4개의 칸으로만 흐른다
  2. 각각의 칸에 대해서, 현재 위치보다 낮은 곳이 주변에 없는 경우, 물은 흐르지 않고, 현재의 칸은 sink가된다.
  3. 그렇지 않으면 물은 인접한 칸들 중 제일 낮은 칸으로 흐른다.
  4. 만약 3번의 경우, 제일 낮은 높이의 인접한 칸이 여러 개 있는 경우, N, W, E, S의 순서대로 흐른다.

  모든 칸의 물은 직접 혹은 간접적으로 흐르게 되고, 이는 sink에서 모이게 된다. 동일한 sink에 모이는 지점들을 하나의 그룹으로
묶는다고 할 때, 그룹들을 알파벳으로 구분해 보자.

C. Welcome to Code Jam

  주어진 string에서 "welcome to code jam"을 만들 수 있는 조합의 경우의 수를 출력하여라. 단 10000으로 나눈 나머지를 구하시오

A. 간단한 패턴 매칭 문제입니다. 입력받은 패턴과 같은 단어가 몇 개가 있는지 찾아보면 됩니다. :)


 1 #include <cstdio>
 2 #include <vector>
 3 #include <string>
 4 #include <iostream>
 5
 6 using namespace std;
 7
 8 int check(string a, string b)
 9 {
10   int pos = 0;
11   for (int i = 0; i < b.size(); ++i)
12   {
13     string word = "";
14     if (a[pos] == '(')
15     {
16       for (int j = pos + 1; ; ++j)
17         if (a[j] == ')')
18         {
19           pos = j + 1;
20           break;
21         }
22         else word += a[j];
23
24     }
25     else 
26     {
27       word = a[pos];
28       pos++;
29     }
30
31     bool isOK = false;
32     for (int j = 0; j < word.size(); ++j)
33       if (word[j] == b[i]) isOK = true;
34     if (!isOK) return 0;
35   }
36
37   if (pos != a.size()) return 0;
38   return 1;
39 }
40
41 int main()
42 {
43   int L, D, N;
44   cin >> L >> D >> N;
45
46   vector<string> word(D);
47
48   for (int i = 0; i < D; ++i)
49     cin >> word[i];
50
51   for (int q = 0; q < N; ++q)
52   {
53     int ret = 0;
54     string str;
55
56     cin >> str;
57     for (int i = 0; i < D; ++i)
58     {
59       if (check(str, word[i])) ret++;
60     }
61     printf("Case #%d: %d\n", q + 1, ret);
62   }
63 }

B. Watersheds

  일단 주어진 지도에서 물이 어느 방향으로 흐르는지를 그래프로 나타낼 수 있습니다. 이 그래프에서 어떤 sink로 도달하는지를 찾아서 같은 sink끼리 묶어주면 됩니다. 저는 어떤 칸에서 물이 흐른다면 이를 무방향성 그래프로 만들어서 같은 그룹을 묶는 방식으로 해결하였습니다.


  1 #include <iostream>
  2 #include <queue>
  3 #include <vector>
  4 #include <cstdlib>
  5 #include <algorithm>
  6
  7 using namespace std;
  8
  9 int table[101][101];
 10 vector< int > graph[101][101];
 11 char ret[101][101];
 12 char ch;
 13
 14 int dx[4] = {-1, 0, 0, 1};
 15 int dy[4] = {0, -1, 1, 0};
 16
 17 void go(int x, int y)
 18 {
 19     queue<pair<int, int> > Q;
 20     Q.push( make_pair( x, y ));
 21
 22     ret[x][y] = ch;
 23     while (!Q.empty())
 24     {
 25         pair<int, int> now = Q.front(); Q.pop();
 26         
 27         x = now.first, y = now.second;
 28         for (int i = 0; i < graph[x][y].size(); ++i)
 29         {
 30             int nx = x + dx[ graph[x][y][i] ];
 31             int ny = y + dy[ graph[x][y][i] ];
 32
 33             if (ret[nx][ny] == '?')
 34             {
 35                 ret[nx][ny] = ch;
 36                 Q.push(make_pair( nx, ny ));
 37             }
 38         }
 39     }
 40 }
 41
 42 int main()
 43 {
 44     int T;
 45     cin >> T;
 46
 47     int n, m;
 48
 49     for (int q = 1; q <= T; ++q)
 50     {
 51         cin >> n >> m;
 52         for (int i = 0; i < n; ++i)
 53             for (int j = 0; j < m; ++j)
 54             {
 55                 cin >> table[i][j];
 56                 graph[i][j].clear();
 57                 ret[i][j] = '?';
 58             }
 59
 60         for (int i = 0; i < n; ++i)
 61         {
 62             for (int j = 0; j < m; ++j)
 63             {
 64                 bool isSink = true;
 65                 int mn = table[i][j];
 66                 int p = -1;
 67
 68                 for (int k = 0; k < 4; ++k)
 69                 {
 70                     int nx = i + dx[k], ny = j + dy[k];
 71                     if (nx < 0 || nx == n || ny < 0 || ny == m) continue;
 72                     if (table[i][j] > table[nx][ny]) isSink = false;
 73                     if (mn > table[nx][ny])
 74                     {
 75                         mn = table[nx][ny];
 76                         p = k;
 77                     }
 78                 }
 79
 80                 if (isSink) continue;
 81
 82                 graph[i][j].push_back( p );
 83                 graph[i + dx[p]][j + dy[p]].push_back( 3 - p );
 84             }
 85         }
 86
 87         ch = 'a';
 88         for (int i = 0; i < n; ++i)
 89         {
 90             for (int j = 0; j < m; ++j)
 91             {
 92                 if( ret[i][j] == '?' )
 93                 {
 94                     go(i, j);
 95                     ch++;
 96                 }
 97             }
 98         }
 99         cout << "Case #" << q << ":" << endl;
100         for (int i = 0; i < n; ++i)
101         {
102             for (int j = 0; j < m; ++j)
103                 cout << ret[i][j] << ' ';
104             cout << endl;
105         }
106     }
107     return 0;
108 }


C. Welcome to Code Jam

  전형적인 DP 문제입니다... 10000으로 나눈 나머지는 고등학교때 배우는 나머지 정리를 이용하시면 구할 수 있습니다.
 (A + B) % C = ((A % C) + (B % C)) % C

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <sstream>
 4
 5 using namespace std;
 6
 7 int T;
 8 string s = "welcome to code jam";
 9 int table[505][25];
10
11 int main()
12 {
13   string str;
14   char tmp[1005];
15
16   fgets(tmp, 1000, stdin); str = tmp;
17   istringstream sin(str); sin >> T;
18   
19   for (int Q = 1; Q <= T; ++Q)
20   {
21     fgets(tmp, 1000, stdin); str = tmp;
22     memset(table, 0, sizeof(table));
23
24     for (int i = 0; i < str.size(); ++i)
25     {
26       for (int j = 0; j < s.size(); ++j)
27       {
28         if (i != 0) table[i][j] = table[i - 1][j];
29         if (str[i] == s[j])
30         {
31           if (j == 0) table[i][j]++;
32           else if (i > 0) table[i][j] += table[i - 1][j - 1];
33         }
34         table[i][j] %= 10000;
35       }
36     }
37
38     printf("Case #%d: %04d\n", Q, table[str.size() - 1][s.size() - 1]);
39   }
40 }


혹시 궁금하신 점이 있으시면 언제라도 댓글 환영합니다. :D