개요
어제 (03/01) 저녁 9시부터 10시 40분까지 진행된 Atcoder Beginner Contest 395 후기입니다.
총 7문제 중 5문제를 풀었습니다. A ~ E번까지 문제를 보자마자 해답은 바로 떠올랐지만, 코드를 작성하는 시간이 오래 걸렸습니다. F번, G번 문제를 읽고나서 도저히 바로 해답이 안떠올라서 대회를 그대로 종료했습니다.
풀이
해설은 꼭 문제를 한번 읽고 확인해주세요.
A - Strictly Increasing?
1
2
N 개의 숫자가 주어집니다.
N 개의 숫자들이 엄밀하게 증가하는 수열로 주어졌는지 판단하면 됩니다.
그냥 구현하면 됩니다.
B - Make Target
1
2
3
자연수 N이 주어집니다.
문제 규칙에 맞게 `#`과 `.`을 찍으면 됩니다.
수식으로 바로 해결해도 되고, N의 범위가 작기 때문에 반복문으로 돌려도 충분히 해결됩니다.
C - Shortest Duplicate Subarray
1
2
3
N 개의 숫자가 주어집니다.
주어지는 수열에서 `중복되는 숫자가 있는 부분 수열 중 최소 길이`를 구해야 합니다.
언뜻보면 브루트포싱으로 할 수 있겠다 싶지만, 숫자 범위가 그렇지 않습니다. 곧바로 각 숫자마다 분류하여 index를 저장했고, 각 index를 훑으면서 최소 격차를 가진 곳을 찾아 반환했습니다.
(처음에 문제를 잘못 읽어서 중복된 숫자가 없는 수열로 보았다가 시간 낭비를 했습니다.)
D - Pigeon Swap
1
2
3
4
5
해당 문제에서는 3가지의 연산이 있습니다.
1. 비둘기 한 마리가 이동한다.
2. 두 둥지에 있는 비둘기들이 서로 다 바꾼다.
3. A번 비둘기가 어디있는지 출력한다.
저는 이 문제를 보자마자, 그냥 어? 둥지 안에 있는 비둘기를 서로 바꾸는게 아니라 둥지에 가상의 라벨이 붙어있다고 생각하고, 그 라벨을 바꿔 붙였다고 생각하면 되는거 아닌가? 라고 생각을 했습니다.
그래서 비둘기마다 위치하는 둥지 위치, 각 둥지(번호를 매겨놓은)마다 붙어 있는 라벨, 각 라벨마다 붙어있는 둥지 원래 번호를 각각 저장했고 제 연산마다 적재적소로 활용해서 문제를 풀이했습니다.
어찌보면 포인터를 활용했다고 할 수 있겠네요.
아래는 코드의 일부 내용입니다
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
def solve():
N, Q = mii()
pigeon_place = [i for i in range(0, N)]
place_label = [i for i in range(0, N)]
place_label_rev = {}
for i in place_label:
place_label_rev[i] = i
for _ in range(Q):
commands = mii()
if commands[0] == 1:
a, b = commands[1:]
a -= 1; b -= 1
pigeon_place[a] = place_label_rev[b]
elif commands[0] == 2:
a, b = commands[1:]
a -= 1; b -= 1
A = place_label_rev[a]
B = place_label_rev[b]
place_label[A], place_label[B] = place_label[B], place_label[A]
place_label_rev[a], place_label_rev[b] = B, A
else:
a = commands[1]
a -= 1
print(place_label[pigeon_place[a]] + 1)
E - Flip Edge
1
2
3
4
5
그래프가 주어집니다.
이때 1번 노드에서 N번 노드로 이동하면서 최단 거리를 알아내야 합니다.
단, 각 간선의 길이는 무조건 1입니다.
그리고 모든 간선의 방향을 뒤바꾸는 연산을 하면서 X 비용을 낼 수도 있습니다.
저는 문제를 보고, 이건 무조건 다익스트라 알고리즘으로 하면 되겠다 였고, 단 거리를 저장하는데 있어서 Distance[어느 방향으로 이 노드에 도달했는가? (0: 정방향, 1: 역방향)][노드 번호]와 같이 거리를 저장하기로 했고 각 노드에서 다시 방향을 유지하여 갈때는 원래 비용인 1을 사용하고, 방향을 바꿔서 갈때는 X + 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
struct Edge {
ll node;
ll cost;
ll direction;
Edge(ll node, ll cost, ll direction) : node(node), cost(cost), direction(direction) {}
bool operator<(const Edge &to) const {
return cost > to.cost;
}
};
ll N, M, X;
vector<vector<vector<Edge> > > edges;
ll dist[2][220000];
ll dijkstra(ll s) {
priority_queue<Edge> pq;
pq.push(Edge(s, 0ll, 0));
pq.push(Edge(s, X, 1));
dist[0][s] = 0;
dist[1][s] = X; // 모든 엣지를 역방향으로 바꾸면서 시작하는 경우
while (!pq.empty()) {
Edge cur = pq.top();
pq.pop();
if (cur.cost > dist[cur.direction][cur.node]) continue;
// 만약 정방향으로 간다면
for(auto nxt : edges[cur.direction][cur.node]) {
if (dist[cur.direction][nxt.node] > cur.cost + nxt.cost) {
dist[cur.direction][nxt.node] = cur.cost + nxt.cost;
pq.push(Edge(nxt.node, dist[nxt.direction][nxt.node], cur.direction));
}
}
// 만약 역방향으로 바꿔서 간다면
for(auto nxt : edges[1 - cur.direction][cur.node]) {
if (dist[1 - cur.direction][nxt.node] > cur.cost + X + nxt.cost) {
dist[1 - cur.direction][nxt.node] = cur.cost + X + nxt.cost;
pq.push(Edge(nxt.node, dist[1 - cur.direction][nxt.node], 1 - cur.direction));
}
}
}
return min(dist[0][N], dist[1][N]);
}
void solve() {
for1(0, M) {
ll a, b; cin >> a >> b;
edges[0][a].push_back(Edge(b, 1, 0));
edges[1][b].push_back(Edge(a, 1, 1));
}
cout << dijkstra(1);
}
F - Smooth Occlusion
- 풀이 X..
G - Minimum Steiner Tree 2
- 풀이 X..
결론
무난하게 5문제를 풀이하고나서, F, G번을 트라이할만한 시간이 남은 competition이었습니다. 다만, 오랜 기간동안을 손을 놓아서인지 구현 속도가 느리기도 했고 조금이라도 어려운 요소가 섞이니 접근이 잘 안되고 있습니다. 백준에서 골드/플레 문제 풀이를 해야할 것 같습니다..