개요
어제 (03/22) 저녁 9시부터 10시 40분까지 진행된 Atcoder Beginner Contest 398 후기입니다.
총 7문제 중 6문제를 풀었습니다.
A번부터 D번까지 풀이하는데 20분을 소모했고, E번이 interactive 문제였고, 아이디어가 떠오르지 않아 F번 먼저 풀이하였고 이때 20분 정도 시간이 걸렸습니다. 그 이후, E번 풀이를 떠올리고 풀이하는데 25분 가량 걸렸습니다. 그리고도 시간이 남아서 G번을 확인하였습니다. 다만, 이때까지도 모든 문제를 풀이한 사람이 없던 상황이었고, G번의 난이도가 쉽지 않다는 것을 알게 되었습니다. 여러 접근을 했지만 풀이를 알아내지 못하고 대회가 종료되었습니다.
풀이
해설은 꼭 문제를 한번 읽고 확인해주세요.
A - Doors in the Center
문제 내용
1
- 와 = 로 구성된 팰린드롬 문자열을 만드는 문제이다.
풀이
주어지는 N이 홀수인지, 짝수인지에 따라 문자열을 구성하면 된다.
B - Full House 3
문제 내용
1
7개의 숫자가 주어진다. 이 숫자를 조합하여 풀하우스를 만들 수 있는지 구하면 된다.
풀이
서로 다른 숫자 a, b에 대해, a의 개수는 3개 이상, b의 개수는 2개 이상인지 검사하면 된다.ㄴ
C - Uniqueness
문제 내용
1
2
3
1 ~ N 번 사람이 각자 숫자를 가지고 있다.
다른 사람들이 가지고 있지 않는 사람들 중에, 가지고 있는 숫자가 가장 큰 사람의 번호를 반환해야 한다.
풀이
솔직히 지문을 읽고, 뭔 이상한 소리인가 싶었고, 예제 또한 이상하게 주어져있어서 조금 당황했다. discussion에서 다른 사람들도 헷갈릴 여지가 있었던 것으로 보인다.
위에 문제 내용을 그대로 구현하면 된다.
D - Bonfire
문제 내용
1
2
모닥불에서 연기가 생성된다.
각 시간(틱)마다 바람이 분다. 이때 특정 (R, C)에 있는 사람에게 연기가 닿았는지 확인하여 모든 시간마다의 결과를 출력한다.
풀이
원래라면 모닥불로 하여금 생긴 연기를 계속 움직여가며 판단할 수 있다. 하지만 연기의 최대 개수가 200,000 개 이기 때문에 N^2이 되는 순간 해결할 수가 없다. 그래서 문제를 보자마자 바로 구현하기 시작한건 연기를 고정시키고 모닥불(0, 0)과 사람 (R, C)을 계속 이동시키자였다.
아래와 같이 구현했다. 다만 좌표를 저장할때 특정 int value로 담아두고 싶어서 좌표를 변환하여 했다. 지금 생각해보면 그냥 tuple로 저장해도 되었을 텐데라는 아쉬움이 남는다.
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
DIFF = 400000
K = 10000000
def to_axis(y, x):
return y * K + x
def solve():
n, r, c = mii()
s = inp()
maker = [DIFF, DIFF]
dy = { 'N': 1, 'S': -1, 'W': 0, 'E': 0 }
dx = { 'N': 0, 'S': 0, 'W': 1, 'E': -1 }
r += DIFF
c += DIFF
smokes = {}
ans = ""
for i in range(n):
direction = s[i]
axis = to_axis(*maker)
smokes[axis] = True
maker[0] += dy[direction]
maker[1] += dx[direction]
r += dy[direction]
c += dx[direction]
if smokes.get(to_axis(r, c), False):
ans += "1"
else:
ans += "0"
print(ans)
E - Tree Game
문제 내용
1
2
3
4
5
트리가 주어진다. 이때 트리에 간선을 추가하는 액션을 각 턴마다 진행한다.
단, 간선을 추가함으로서 홀수개의 노드로 구성된 cycle이 생기면 안된다.
더이상 추가할 수 있는 간선이 없는 경우 패배한다.
상대와 게임을 진행함에 있어서, 선공/후공을 정하여 승리해야 한다.
풀이
처음에는 인터랙티브 문제이기도 하고 풀이가 잘 떠오르지 않았다. 그러던 중 예시를 여러 개 만들어보다가 떠오른 생각이 있었다.
처음에 주어지는 트리 상에서, 서로의 거리가 홀수로 떨어져 있는 경우면서 바로 이어지지 않은 경우가 결국 간선을 만들어낼 수 있는 경우 아닌가?
정점의 개수 N이 최대 100까지였기 때문에 구현을 빠르고 쉽게하기 위해, 플로이드-와샬로 미리 거리를 구했고, 서로의 거리가 홀수로 떨어져 있는 경우면서 바로 이어지지 않은 경우 == ar[x][y] % 2 == 1 && ar[x][y] > 1에 대한 간선을 미리 구해두었다.
그래서 이 간선들을 토대로 내 턴에는 아무거나 출력하고, 상대 턴에는 주어지는 간선을 제거하면서 처리해봤다.
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
ll ar[110][110];
void solve() {
ll N;
cin >> N;
for(int i = 0; i <= N; i++) {
for(int j = 0; j <= N; j++) {
ar[i][j] = INF;
}
ar[i][i] = 0;
}
for(int i = 1; i < N; i++) {
int a, b;
cin >> a >> b;
ar[a][b] = 1;
ar[b][a] = 1;
}
for(int z = 1; z <= N; z++) {
for(int x = 1; x <= N; x++) {
for(int y = 1; y <= N; y++) {
if(ar[x][y] > ar[x][z] + ar[z][y]) {
ar[x][y] = ar[x][z] + ar[z][y];
}
}
}
}
vector <pii> ans_list;
for(int x = 1; x <= N; x++) {
for(int y = x + 1; y <= N; y++) {
if(ar[x][y] % 2 == 1 && ar[x][y] > 1) ans_list.push_back({ x, y });
}
}
if(ans_list.size() % 2 == 0) {
cout << "Second" << endl;
} else {
cout << "First" << endl;
cout << ans_list[0].first << " " << ans_list[0].second << endl;
ans_list.erase(ans_list.begin());
}
while(1) {
int a, b;
cin >> a >> b;
if(a == -1 && b == -1) return;
if (a > b) {
swap(a, b);
}
for(int i = 0; i < ans_list.size(); i++) {
pii current = ans_list[i];
if(current.first == a && current.second == b) {
ans_list.erase(ans_list.begin() + i);
break;
}
}
cout << ans_list[0].first << " " << ans_list[0].second << endl;
ans_list.erase(ans_list.begin());
}
}
F - ABCBA
문제 내용
1
문자열 S가 주어졌을 때, 문자열 S를 prefix로 하는 팰린드롬을 만들어야 한다.
풀이
보자마자 manacher 알고리즘이 떠올랐다. manacher 알고리즘은 특정 위치를 중심으로 팰린드롬의 길이를 구할 수 있는 알고리즘이다. 만약 이렇게 어떤 위치에서 구한 팰린드롬이 문자열 끝까지 도달할 수 있다면, 문제에서 원하는 문자열 S를 prefix로 하는 팰린드롬을 만들 수 있는 상황일 것이다. 따라서 앞에서부터 순차적으로 확인하다가 해당 경우인경우 바로 출력하게 했다.
단, 이때 홀수 길이의 팰린드롬과 짝수 길이의 팰린드롬인지에 따라 약간의 구현 처리가 필요하다.
아래 코드는 manacher 알고리즘의 일부 구현 내용을 생략하여 문제에 맞게 활용한 코드이다.
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
vector<int> manacher(string& s){
int n = s.size(), R = -1, p = -1;
vector<int> A(n);
for(int i=0; i<n; i++){
if(i <= R) A[i] = min(A[2*p-i], R-i);
while(i-A[i]-1 >= 0 && i+A[i]+1 < n && s[i-A[i]-1] == s[i+A[i]+1]) A[i]++;
if(i+A[i] > R) R = i+A[i], p = i;
}
return A;
}
string space(string& s){
string t;
for(char c: s) t+= c, t+= ' ';
t.pop_back();
return t;
}
void solve() {
string s, o;
cin >> s;
o = s;
int n = s.length();
s = space(s);
vector <int> ret_1 = manacher(s);
int k = ret_1.size();
int ans = ret_1.size() - 1;
for(int i = 0; i < k; i++) {
if (i + ret_1[i] == k - 1) {
ans = i;
break;
}
}
if(ans % 2 == 0) {
int org_idx = ans / 2;
for(int i = 0; i <= org_idx; i++) {
cout << o[i];
}
for(int i = org_idx - 1; i >= 0; i--) {
cout << o[i];
}
} else {
int org_idx = ans / 2;
for(int i = 0; i <= org_idx; i++) {
cout << o[i];
}
for(int i = org_idx; i >= 0; i--) {
cout << o[i];
}
}
}
G - Not Only Tree Game
문제 내용
1
2
3
4
5
E번에서 주어지는 문제 조건과 유사하다.
단, 해당 문제에서는 트리가 아닌 그래프가 주어진다.
심지어 서로 연결되어 있지 않는 경우도 존재한다.
이때 2명의 플레이어가 게임을 진행한다고 했을 때 어떤 플레이어가 이기는지 출력해야 한다.
풀이
풀이가 전혀 떠오르지 않았다. 에디토리얼은 여기 있다.
결론
그래도 7문제중 6문제를 무난하게 풀이한 contest 였다. 오랫동안 굳었던 머리가 다시 풀리는 느낌이라 좋았던 대회지만, 대회 자체의 문제 난이도와 배치는 조금 이상했던 것 같다.