[Atcoder] AtCoder Beginner Contest 399 후기

서론

불맛이 나는 컨테스트였습니다. (이게 Beginner?)

Problem

A

길이가 갚은 문자열 2개가 주어질 때, 각 문자를 비교했을 때 다른 게 몇 개 있는지 세는 문제입니다.

B

사람 1부터 N까지 번호가 주어지고 사람마다 점수가 존재하면, 이 점수를 기반으로 랭크를 매기는 문제입니다.

만약 동률(Tie)일시 낮은 순위로 통일합니다.

저는 ~pair<int, int>~ 형태로 벡터에 넣어 정렬한 후 각 $index$에 해당하는 $rank$를 매기는 식으로 구현했습니다.

에디토리얼에서는 naive하게 $O(n^2)$알고리즘을 제시합니다.

C

그래프 $G$가 주어질 때, Forest로 만들기 위해 제거해야 하는 최소한의 간선 개수를 구하는 문제입니다.

사실, 이 문제는 그래프 $G$의 Cycle 개수를 구하는 문제와 완전히 동치입니다!!

사이클을 판별하는 알고리즘은 크게 두 가지가 있는데, 하나는 DFS를 응용한 풀이와, Union-Find를 이용한 풀이입니다.

저는 전자를 이용해 풀었습니다.

D

두 개씩 순서쌍을 묶을 때, 서로 짝이 안맞는 순서쌍이 여러 개 있으면 최소한 두 순서쌍은 서로 매칭되는 순서쌍을 가집니다.

이 경우에만 swap을 고려하면, 풀 수 있는 문제입니다.

실전에서는 이런 그리디한 접근을 하기 어려웠습니다.

E와 F는 스킵하도록 하겠습니다..

정리

C번에서 멘탈이 갈렸던 콘테스트였습니다.. 헷갈린 개념이 있었네요.

저는 어떤 간선이 지워지면 사이클을 두 개 이상 지울 수 있는 것으로 알아버려서, 그런 간선을 찾는데 멘탈이 갈려버린 문제였습니다.

물론 간선이 지워지면, 그 간선을 포함하는 사이클 전부가 깨질 수 있으나, 독립적인 사이클 수(cyclomatic number)는 정확히 하나 줄어듭니다.

그래서 자포자기 하는 심정으로 그냥 사이클의 개수만 파악하는 알고리즘을 썼더니 풀렸던 문제입니다..

D번부터는 시간도 없고, 어렵기도 하고 해서 못풀었네요.