[Atcoder] ABC 401 후기

https://atcoder.jp/contests/abc401/tasks

코드
https://github.com/kss418/Atcoder/tree/main/ABC/400/401

A (0:55)

단순 IF문 Case Work 문제

B (2:47)

문자열로 private가 왔을 때 logout이 가까우면 +1 아니면 넘어가면 됨

C (5:31)

M 이전 까지의 값은 1로 만들어 주고
그 이후의 값들은 누적합으로 O(1)에 처리 해주면 O(N)에 풀 수 있음

D (96:16, -6)

C까지 5분만에 풀고 넘어왔는데 떠오르는게 없어서 바로 E로 넘어갔었는데 굉장히 잘한 선택이었다.

첫 번째 풀이
배치 할 수 있는 O의 개수 보다 배치 해야 하는 O의 개수와 같으면 앞에서 부터 O를 채워주고 아니면 O와 인접한 ?만 .으로 바꿔주고 그대로 출력

3 2 
???

위와 같은 입력이 오면 O.O가 정답이지만 내 코드는 ???를 출력 하는 반례가 있었다.

두 번째 풀이
앞에서부터 O를 채웠을 때랑 뒤에서 부터 O를 채웠을 때의 문자열의 인덱스가 같으면 그 인덱스의 값을 출력하고 아니면 ?를 출력하고 O를 최대한 많이 배치했을 때 M의 값보다 크다면 그냥 S를 출력

3 1
?O?

하지만 위와 같이 이미 O를 다 배치했으면 나머지 ?는 자동으로 .가 되어야 하는데 예외처리를 안해서 추가적으로 여러번 더 틀렸다.

E (41:47)

일단 정점의 간선을 제거하는 연산을 보고 바로 유니온 파인드를 떠올렸다. 간선을 제거하는 연산을 거꾸로 하면 간선을 생성하는 연산이 되는데, 이 때 유니온 파인드를 활용 할 수 있다.

1에서 도달 할 수 있는 정점의 집합이 $\{1 ~...~ i\}$ 가 될 때 연산의 최솟값을 구하려면 $\{1 ~...~ i\}$을 하나의 연결 요소로 보고$\{i + 1 ~...~ N\}$ 정점 중에서 $\{1 ~...~ i\}$와 인접한 정점만 제거 해 주면 된다.

내 풀이는 N -> 1 순서대로 순회 했기 때문에 어떤 정점이 3, 4, 5 정점과 인접하다면 i가 2가 될 때 까지는 1과 연결 된 그래프와 그 정점은 인접하게 된다. 결국 어떤 정점과 인접한 가장 작은 정점 보다 작은 정점을 순회 하기 전 까지는 그 정점은 1와 연결된 그래프와 인접하게 된다.

그래서 최소 우선순위 큐에 인접한 가장 작은 정점을 넣고 각 답은 우선순위 큐의 크기로 구해줬다.

또한 답을 구할 때 집합이 $\{1 ~...~ i\}$여야 하는데 $\{i + 1 ~...~ N\}$중의 정점을 포함하지 않고는 $\{1 ~...~ i\}$를 만들 수 없는 경우가 생기는데 이는 유니온 파인드로 판단해줬다.

F (-)

D번에서 삽질을 많이 해서 건들지도 못했다.

첫 번째 트리의 i와 두 번째 트리의 j 정점을 연결하면 첫 번째 트리의 루트가 i일 때 트리의 높이 $H1_{i}$, 두 번째 트리의 루트가 j일 때 트리의 높이 $H2_{j}$ 일 때 트리의 지름은 $H1_{i} + H2_{j} + 1$ 가 된다.

그래서 처음에 생각 한 풀이는 첫 번째 트리의 모든 높이와 두 번째 트리의 모든 높이를 Rerooting DP로 구한 다음 두 합을 곱한 뒤 경우의 수 만큼 +1을 해주는 것이였다.

하지만 첫 번째 트리나 두 번째 트리의 지름이 두 트리를 합한 지름보다 크면 각 트리의 지름을 사용해야 한다.

결국 여기에서 막혀서 에디토리얼을 봤다.
각 트리의 높이를 정렬해 놓으면 $H1_{i} + H2_{j} + 1$는 단조 증가 하기 때문에 어느 순간부터는 두 트리의 지름보다 두 트리를 합한 지름이 커지게 된다.

이는 이분 탐색이나 슬라이딩 윈도우 기법으로 해결 할 수 있는데, 처음에 이분 탐색으로 접근했다가 인덱스를 잘 못 잡았는지 자꾸 답이 틀리게 나와서 슬라이딩 윈도우로 코드를 바꿔서 겨우 맞췄다.