[Atcoder] AtCoder Beginner Contest 398 후기

서론

해시, 트리를 사용한 집합과 맵 자료구조에 매우 취약했다는 것을 배웠던 컨테스트 였습니다.

Problem

A

문자열의 중앙을 찾는.. 어찌보면 if-문 만 잘 써도 되는 쉬운 문제였네요.

B

숫자의 개수를 세서 압축하고, 이를 내림차순 정렬해서 첫 번째 원소가 3 이상이고 두 번째 원소가 2개 이상임을 알아내기만 하면 되는 문제였습니다.

C

유일한 원소 중 $index$가 제일 큰 원소를 찾는 문제입니다.

map을 이용해 정렬 상태를 유지하면서, $value$가 1인 원소 중 가장 오른쪽에 있는 원소의 최대 $index$를 출력하면 됩니다! 각 원소의 최대 $index$를 저장하는 건 unordered_map을 이용합니다.

D

발상의 전환이 중요한 문제였는데, 각 문자에 대해 연기는 항상 생성되니, 불과 사람을 옮기는 발상을 하는게 중요했던 문제입니다.

여기서 모든 연기에 대해 빠르게 탐색을 진행하고, 삽입이 계속 이루어 지기 때문에 set을 이용해 연기들을 저장하고, 이 연기 set에서 사람이 있는 좌표를 찾기만 하면 되는 문제였습니다.

실전에서는 연기를 계속 어떻게 움직여야하는지만 고민했어서 구현조차 못했습니다..

E

두 명이서 트리 $G$가 주어지고 두 Vertex를 골라서 edge를 이어 상대가 두 Vertex를 고를 수 없게 만드는 게임을 합니다.

게임의 순서(선/후)를 정할 수 있고, 다음과 같은 조건을 만족하는 Vertex를 고를 수 있습니다.

조건 1. 두 Vertex간에 edge가 존재하지 않아야 합니다.

조건 2. 만들어진 간선이 edge의 개수가 홀수인 cycle(odd cycle)을 생성하지 않아야 합니다.

이 문제는 쉽게 변형하면 홀수 사이클을 생성하지 않는다는 것에 포커스를 둬, 이분 그래프 문제로 바꿔 partial set $A$, $B$간의 원소에 계속 edge를 이어주는 게임을 하는 것입니다.

자기 턴에 이을 수 있는 엣지가 존재하지 않는다면, 패배합니다.

이를 이용하면, 추가할 수 있는 엣지는 $\left

A \right

\times \left

B \right

$임을 알 수 있습니다.

트리는, DAG 이여서 이분 그래프이고, 총 edge의 개수는 $N -1$개입니다.

정리하면, 트리 $G$가 주어진다면, $(\left

A \right

\times \left

B \right

- N + 1)$개의 경우의 수를 가진다는 것이고, 이 경우의 수가 홀수면 차례를 선으로 하면 되고, 짝수면 후로 하면 됩니다.

이 후 알고리즘은

먼저 DFS를 통해 이분 집합을 구하고, 후보 간선을 생성해, interaction 단계에서 간선들을 지워나가면 됩니다.

F

분명 KMP로 비슷한 문제를 풀어봤던 것 같은데, KMP가 기억 속에 남아있지 않았습니다.. 에디토리얼에서는 Manacher 알고리즘을 이용해 풀었습니다.

정리

KMP 알고리즘과 Manacher 알고리즘을 배울 건데.. 이제 곧 중간고사 시즌이라 시간이 날지 모르겠습니다.

빠른 시일 내에 복습/학습 할 예정입니다.