개요
어제 (03/08) 저녁 9시부터 10시 40분까지 진행된 Atcoder Beginner Contest 396 후기입니다.
총 7문제 중 5문제를 풀었습니다. A ~ D번까지 문제를 보자마자 바로 풀이하였고, 21분 소요했습니다. 여전히 구현이 느립니다. 더 땡겨야 합니다. E번 문제를 대강 풀이하고 제출했는데, 최적화된 해답을 출력하지 않았고, 이를 해결하는데 시간을 오래 사용했습니다. 마지막 제출을 대회 종료 5초전에 했고, 대회가 종료된 후 AC를 확인했습니다.
풀이
해설은 꼭 문제를 한번 읽고 확인해주세요.
A - Triple Four
1
3번 연속된 숫자가 있는 경우, Yes 아니면 No를 출력한다.
문제에 주어지는대로 바로 구현하면 됩니다.
B - Card Pile
1
스택에 카드를 넣는 연산과 맨 위의 카드를 확인한 후, 빼는 연산 구현
문제에서 주어지는대로 스택을 사용하면 됩니다. 단, 100개의 0을 이미 넣어놓은채 시작하는 전제조건을 확인해야 합니다.
C - Buy Balls
1
2
3
검정색 공들과 흰색 공들이 숫자가 적혀진 채로 주어진다.
각 공을 고르고, 고른 공의 숫자들을 합쳤을 때 최대가 되도록 해야 한다. 단, 고른 검정색 공의 수가 흰색 공의 수보다 크거나 같아야 한다.
아래와 같이 그리디하게 최대한 검정, 흰색을 동시에 선택하다가, 흰색공을 선택하지 않아도 되는 경우에는 검정색만 고르도록 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solve():
B = sorted(B, reverse=True)
W = sorted(W, reverse=True)
s = 0
for i in range(min(n, m)):
if B[i] + W[i] > 0 and W[i] > 0:
s += B[i] + W[i]
elif B[i] > 0:
s += B[i]
for i in range(min(n, m), n):
if B[i] > 0:
s += B[i]
return s
D - Minimum XOR Path
1
2
3
그래프가 주어진다. 그래프의 간선에 가중치가 주어진다.
다만, 해당 가중치를 더하는 연산이 아닌, XOR 연산을 수행했을 때, 1 ~ N 까지 단순 경로로 도달했을 때 최소 값을 구하라
N이 크지 않게 주어졌다. DFS로 모든 단순 경로를 탐색하도록 했다. 아래에 일부 코드를 적어두었다.
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
n = m = 0
edges = []
mn = []
chk = []
def dfs(node, label):
global n, m, edges, mn, chk
if chk[node]:
return
chk[node] = True
mn[node] = min(mn[node], label)
for edge in edges[node]:
dfs(edge[0], label ^ edge[1])
chk[node] = False
def solve():
global n, m, edges, mn, chk
dfs(1, 0)
print(mn[n])
E - Min of Restricted Sum
문제가 복잡하게 주어졌지만, 요약하자면 다음과 같다.
1
2
3
노드 번호1, 노드번호2, 두 노드 사이의 가중치가 나열된다.
각 노드마다의 값을 구해야 한다. 이때 각 노드 사이의 값 끼리 XOR연산을 했을 때 주어지는 가중치와 동일하도록 해야 한다.
문제를 보다보니, XOR 연산의 특성을 고민해보다 결국 시작 노드에서 아무 값으로 시작해도 그래프가 정상적으로 주어졌다면 어떻게든 값이 나온다는 사실을 알았다. 그래서 무작정 각 노드마다 탐색을 해서, 탐색이 되지 않은 경우 0으로 시작해서 그래프를 탐색하도록 했다.
하지만, 이는 틀린 답이었고, 이유를 찾지 못하다가 뒤늦게 문제 상 주어진 조건을 놓쳤음을 알게 되었다.
If there are multiple good sequences with the same minimum sum, printing any of them is accepted.
그럼 최소를 어떻게 찾아야할까를 계속 고민하다가, 각 그래프 탐색을 하면서 탐색이 된 노드들을 그룹지어놓고, 각 그룹마다 1, 2, 4, 8, 16, … 를 모든 노드값에 XOR 연산을 하면서 최소값이 된 경우 갱신을 하는식으로 구현을 추가했다.
해당 구현을 하다가 조금 구현 실수를 하면서 WA를 계속 맞았지만, 대회 종료 직전에 제출한 코드가 AC를 받으면서 종료되었다.
결론
이번에는 E번 문제를 좀 쉽게 접근하고나서, 더 생각이 떠오르지 않아 망설임이 많았습니다. XOR 연산에 대해서 좀더 잘 알게 된 competition이었던 것 같습니다.