Pattern Matching
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
\(N\)개의 문자열 패턴이 들어온다.
이 문자열 패턴은 알파벳 대문자와 1개 이상의 애스터리스크(*)로만 이루어져 있는데,
애스터리스크에는 어떤 문자열이든 대응이 가능함을 말한다.
이때, 모든 문자열 패턴을 만족하면서 길이가 \(10^4\)이하인 문자열이 존재하는지 알아내야 한다.
만약 존재한다면, 그 문자열을 출력한다.
문자열 패턴의 맨 처음부터 시작해 애스터리스크가 나오기 직전까지의 문자열을 접두사라고 하자.
모든 문자열 패턴의 접두사중 가장 긴것에 대해, 다른 모든 접두사는 이 접두사의 접두사여야 한다.
접미사의 경우에도 마찬가지이고, 그렇지 않은 경우가 있다면 답을 만드는 것은 불가능하다.
그리고 모든 애스터리스크 사이에 있는 문자열들은 한 패턴 내에서의 순서만 지켜진다면 어디에서 등장하든 상관없다는 사실을 알 수 있다. 이 문자열들을 중간 문자열이라고 하자.
그러므로,
가장 긴 접두사 + 모든 중간 문자열 + 가장 긴 접미사
는 답중 하나가 된다.
\(N\)이 최대 \(50\)이고, 문자열의 길이는 최대 \(100\)이므로 우리가 만든 문자열의 길이는 \(10^4\)를 넘지 않는다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
vector <string> pfx, sfx, rest;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int t = 1; t <= T; t++)
{
pfx.clear();
sfx.clear();
rest.clear();
cin >> n;
for (int i = 0; i < n; i++)
{
string tmp; cin >> tmp;
int pfx_idx = tmp.size();
int sfx_idx = -1;
string cpfx, csfx;
for (int j = 0; j < tmp.size(); j++)
{
if (tmp[j] == '*')
{
pfx_idx = j;
break;
}
cpfx += tmp[j];
}
for (int j = tmp.size() - 1; j >= 0; j--)
{
if (tmp[j] == '*')
{
sfx_idx = j;
break;
}
csfx += tmp[j];
}
string crest;
for (int j = pfx_idx; j <= sfx_idx; j++)
{
if (tmp[j] == '*') continue;
crest += tmp[j];
}
pfx.push_back(cpfx);
sfx.push_back(csfx);
rest.push_back(crest);
}
bool isValid = true;
for (int i = 0; i < 100; i++)
{
set <char> st;
for (auto str : pfx)
{
if (str.size() <= i) continue;
st.insert(str[i]);
}
if (st.empty()) break;
if (st.size() > 1) isValid = false;
}
for (int i = 0; i < 100; i++)
{
set <char> st;
for (auto str : sfx)
{
if (str.size() <= i) continue;
st.insert(str[i]);
}
if (st.empty()) break;
if (st.size() > 1) isValid = false;
}
if (!isValid)
{
cout << "Case #" << t << ": *\n";
continue;
}
string lpfx, lsfx;
for (auto str : pfx)
{
if (str.size() > lpfx.size()) lpfx = str;
}
for (auto str : sfx)
{
if (str.size() > lsfx.size()) lsfx = str;
}
reverse(lsfx.begin(), lsfx.end());
cout << "Case #" << t << ": ";
cout << lpfx;
for (auto str : rest) cout << str;
cout << lsfx;
cout << "\n";
}
}
r
|
Pascal Walk
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
수 \(N\)이 주어진다. (\(N \le 10^9\))
파스칼의 삼각형에서 다음과 같은 이동을 하려고 한다.
1. 맨 위의 1부터 시작한다.
2. 한 칸에서 다음 칸으로 이동할 때, 육각형의 면이 인접한 칸으로만 이동할 수 있다.
3. 한번 이동한 칸은 다시 이동할 수 없다.
이 때, 500칸 이내로 이동하여 방문한 경로에 있는 수의 합이 정확히 \(N\)이 되는 경로를 하나 출력해야 한다.
파스칼의 삼각형에서 \(i\)번째 행의 수들의 총 합은 \(2^{i-1}\)이다.
그러면 입력으로 들어오는 \(N\)을 비트가 1에 해당되는 행들을 전부 방문하면 된다고 생각할 수 있는데,
이 행들을 전부 이어주기 위해서 추가적인 칸이 필요하게 된다.
이 방식으로 최대 몇번째 행까지 쓰이는지 생각해보자.
\(2^{30}=1073741824 \gt 10^9\)이므로 최대 30번째 행까지 사용된다.
맨 바깥쪽 1로 이루어진 30칸을 미리 빼서 행들을 잇는 용도로 쓴다고 한다면,
\(N-30\)에 대해 위와 같은 방식으로 비트가 1에 해당되는 행들을 전부 방문하는 식으로 해결할 수 있다.
만약 30행을 전부 사용한다고 했을 때, 사용하는 칸의 개수는 \(30*31/2+30=495\)로, 500칸 이내에 들어감을 알 수 있다.
\(N\)이 30보다 작다면 맨 바깥쪽 1만을 이용해 \(N\)을 만들면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int t = 1; t <= T; t++)
{
int n; cin >> n;
cout << "Case #" << t << ":\n";
if (n < 30)
{
for (int i = 1; i <= n; i++)
cout << i << " 1\n";
continue;
}
n -= 30;
vector <int> rows;
for (int i = 0; i < 30; i++)
{
if (n & (1 << i)) rows.push_back(i + 1);
}
int crow = 0, ccol = 1;
int used = 0;
for (int row : rows)
{
used += row - crow - 1;
if (ccol == 1)
{
while (crow + 1 <= row)
{
crow++;
cout << crow << ' ' << ccol << '\n';
}
while (ccol + 1 <= row)
{
ccol++;
cout << crow << ' ' << ccol << '\n';
}
}
else
{
while (crow + 1 <= row)
{
crow++; ccol++;
cout << crow << ' ' << ccol << '\n';
}
while (ccol - 1 >= 1)
{
ccol--;
cout << crow << ' ' << ccol << '\n';
}
}
}
for (int i = 0; i < 30 - used; i++)
{
if (ccol == 1)
{
crow++;
cout << crow << ' ' << ccol << '\n';
}
else
{
crow++; ccol++;
cout << crow << ' ' << ccol << '\n';
}
}
}
}
|
Square Dance
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
\(R \times C\) 크기의 댄스 플로어에서 댄스 경연대회를 하고 있다.
\(R \times C\)명의 사람들이 각각의 칸에서 춤을 추고 있고, 춤 실력 \(S_{i,j}\)가 주어진다.
어떤 사람의 상하좌우로 (같은 행이나 같은 열에 있는 사람) 가장 가까이 있는 사람들을 compass neighbor라고 하자.
compass neighbor는 최소 0명에서 최대 4명까지 있을 수 있게 되는데, 만약 어떤 사람의 춤 실력이 compass neighbor들의 춤 실력의 평균보다 작다면 다음 라운드에서 탈락하게 된다.
이런 식으로 라운드를 계속해 나가다가 더이상 탈락하는 사람이 없으면, 경연이 종료된다.
라운드의 흥미로움 레벨은 현재 라운드에 생존해 있는 모든 사람들의 춤 실력의 합이고,
경연의 흥미로움 레벨은 모든 라운드의 흥미로움 레벨의 합이다.
이 댄스 플로어의 초기 상태가 주어질 때 경연의 흥미로움 레벨을 구해야 한다.
초기 상태에서 탈락할 사람들을 찾는건 어렵지 않다.
그렇다면 그 다음으로 탈락할 수 있는 사람들의 후보는 초기에서 탈락한 사람들의 compass neighbor이 될 것이다.
그러면 BFS와 비슷한 방식으로, 모든 사람들은 많아도 한번 탈락하고
한번 탈락할 때마다 많아도 4명의 사람들을 다음 탈락후보로서 검사할 수 있기 때문에,
탈락할 사람들을 찾는 것을 총 \(O(RC)\)의 시간에 할 수 있게 된다.
남은 것은 compass neighbor을 빠르게 찾는 방법이다.
어떤 사람이 탈락했을 때, 이 사람의 왼쪽 사람과 오른쪽 사람을 compass neighbor이 되도록 이어주고,
위쪽과 아래쪽 사람을 compass neighbor이 되도록 이어줘야 할 것이다.
다시 말하면, 중간 삭제가 빠른 자료구조가 필요한데, 가장 효율적인것은 Linked List일 것이다.
각 행과 열에 대하여 총 \(R+C\)개의 List를 만들고
모든 사람들에 대해 행과 열 2개의 List에 대한 포인터를 저장해 놓는다면,
탈락 했을 때 \(O(1)\)의 시간복잡도로 내 상하좌우의 사람들을 다시 이어줄 수 있게 된다.
따라서 총 시간복잡도는 \(O(RC)\)이고, \(R \times C \le 10^5\)이므로 충분히 시간안에 동작하게 된다.
*밑의 코드는 set을 사용한 부분이 있어 시간복잡도가 \(O(RC)\)보다는 크지만, 문제를 해결하는데 지장은 없다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int r, c;
struct Node
{
bool isValid;
ll val;
list<pii>::iterator it_row;
list<pii>::iterator it_col;
};
vector<vector<Node> > s;
vector<list<pii> > ls_row;
vector<list<pii> > ls_col;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int t = 1; t <= T; t++)
{
s.clear();
ls_row.clear();
ls_col.clear();
cin >> r >> c;
ll ans = 0;
ll curSum = 0;
s.resize(r);
ls_row.resize(r);
ls_col.resize(c);
for (int i = 0; i < r; i++)
{
s[i].resize(c);
for (int j = 0; j < c; j++)
{
ll x; cin >> x;
curSum += x;
ls_row[i].push_back({ i, j });
ls_col[j].push_back({ i, j });
s[i][j].isValid = true;
s[i][j].val = x;
s[i][j].it_row = prev(ls_row[i].end());
s[i][j].it_col = prev(ls_col[j].end());
}
}
queue <pii> q, tq;
for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
{
q.push({ i,j });
}
ans += curSum;
while (true)
{
while (!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
Node& cNode = s[i][j];
auto cit_row = cNode.it_row;
auto cit_col = cNode.it_col;
ll cVal = cNode.val;
ll sum = 0;
ll cnt = 0;
if (cit_row != ls_row[i].begin())
{
auto it = prev(cit_row);
sum += s[it->first][it->second].val;
cnt++;
}
if (next(cit_row) != ls_row[i].end())
{
auto it = next(cit_row);
sum += s[it->first][it->second].val;
cnt++;
}
if (cit_col != ls_col[j].begin())
{
auto it = prev(cit_col);
sum += s[it->first][it->second].val;
cnt++;
}
if (next(cit_col) != ls_col[j].end())
{
auto it = next(cit_col);
sum += s[it->first][it->second].val;
cnt++;
}
if (cnt == 0) continue;
if (sum > cVal* cnt)
{
cNode.isValid = false;
tq.push({ i,j });
}
}
if (tq.empty()) break;
set <pii> mp;
vector < pair<int, list<pii>::iterator> > er_row, er_col;
while (!tq.empty())
{
int i = tq.front().first;
int j = tq.front().second;
tq.pop();
Node& cNode = s[i][j];
auto cit_row = cNode.it_row;
auto cit_col = cNode.it_col;
ll cVal = cNode.val;
if (cit_row != ls_row[i].begin())
{
auto it = prev(cit_row);
if (s[it->first][it->second].isValid)
mp.insert({ it->first, it->second });
}
if (next(cit_row) != ls_row[i].end())
{
auto it = next(cit_row);
if (s[it->first][it->second].isValid)
mp.insert({ it->first, it->second });
}
if (cit_col != ls_col[j].begin())
{
auto it = prev(cit_col);
if (s[it->first][it->second].isValid)
mp.insert({ it->first, it->second });
}
if (next(cit_col) != ls_col[j].end())
{
auto it = next(cit_col);
if (s[it->first][it->second].isValid)
mp.insert({ it->first, it->second });
}
er_row.push_back({ i, cit_row });
er_col.push_back({ j, cit_col });
curSum -= cVal;
}
for (auto it : er_row) ls_row[it.first].erase(it.second);
for (auto it : er_col) ls_col[it.first].erase(it.second);
ans += curSum;
for (auto it : mp)
{
q.push({ it.first, it.second });
}
}
cout << "Case #" << t << ": " << ans << '\n';
}
}
|
'문제 풀이 > 그외' 카테고리의 다른 글
| Google Kick Start - Round F 2020 (0) | 2020.09.27 |
|---|---|
| Google Kick Start - Round E 2020 (2) | 2020.08.23 |
| SCPC 2020 Round 1 (2) | 2020.08.22 |
| Google Kick Start - Round D 2020 (0) | 2020.07.13 |
| Google Code Jam - Qualification Round 2020 (0) | 2020.04.11 |
