대회후기: Codeforces Round #600 (Div. 2)

AtCoder 대회를 뛰고 거의 연속으로 코포 대회를 진행했다.

---

A: Single Push

간단한 문제이지만, 불일치하는 지점의 개수가 1인 경우에 대한 예외처리를 적절히 하지 않아 이를 급하게 수정하느라 조금의 지체가 있었다.

7분에 AC

---

B: Silly Mistake

조건에 맞도록 주어진 배열을 분할할 수 있는지를 묻는 문제이다. 같은 사원이 같은 날에 두 번 enter할 수 없다는 조건을 놓치고 그냥 전체를 무조건 하루로 잡고 전체 배열이 조건에 맞는지 확인하는 코드를 짰다. 제출하고 WA. 다시 보고 문제점을 확인, 같은 사원이 다시 enter 하려고 하는 순간 새로운 날이 시작되도록 수정하였다. Pretests passed. 하지만 동일 사원이 다시 들어오려 할 때가 아니라, 모든 사원이 다 나간 순간에 새로운 날이 시작되도록 해야 새로운 날이 시작될 때 아직 나가지 못해 걸리는 사원이 없었다. 이 사실을 대회가 끝나고 system testing이 진행될 때에야 알게 되어 WA 추가. What a silly mistake indeed.

29분에 AC, 최종으로 WA

---

C: Sweets Eating

Greedy하게 풀면 되겠지... 라고 생각하고 \(O(n^2)\)의 코드를 짜 버렸다. 바로 TLE.

연산의 횟수를 어떻게 줄일 수 있을지 생각하던 중에 누적합 배열을 떠올렸다. 하지만 누적합 배열만으로는 복잡도가 유의미하게 줄어들지 않아 고민 끝에 누적합 배열의 누적합 배열을 생각하게 되었다. 손으로 몇번 써보고 빠르게 규칙성을 확인한 후, 구현을 간단하게 하였다. 오히려 B보다 빠르게 푼 것 같다.

TLE 후 47분에 AC

---

D: Harmonious Graph

내가 싫어하는 그래프 문제이다. 연결되어 있는 group들로 그래프를 나누고, 각 부분이 연속한 숫자들로 이루어졌는지를 확인하면 해결되는 문제였다. 두 group의 숫자 범위가 overlap하면 그 두 group을 이어주면 된다는 생각을 했다. 여기서 문제가 생겼다. 첫째, 숫자 범위가 overlap되는 모든 group을 어떻게 충분히 낮은 복잡도로 찾을 수 있을지, 그리고 둘째, 어떻게 찾은 두 group을 충분히 낮은 복잡도로 하나로 합할 수 있을지이다. 이러한 문제점들, 그리고 재귀적으로 짠 그래프 탐색 알고리즘이 Python에서 recursionlimit에 부딛히고 또 stack overflow가 터지고 하는 상황을 거치다 보니, 머리가 더이상 생각하기를 거부했다. 머리를 반쯤 꺼두고 편안한 마음으로 문제를 보며 대회 종료를 기다렸다.

 

대회가 끝나고 Nyso의 풀이를 보니 union-find 알고리즘을 사용해 내가 가졌던 모든 문제점을 해결했다. 존재만 알고 있고 원리나 구현법은 모르는 알고리즘이었다. 대회만 뛰지 말고 공부도 좀 하자.

---

총평

Union-find를 몰라서 풀지 못한 D를 제외하면 나쁘지 않게 친 대회이다. 그러나 B가 system test에서 터지면서 결국 2 문제밖에 풀지 못한 대회가 되었다. 조금 더 꼼꼼하게 생각해 보았다면 피할 수 있었을지도 모르는 실수였다. 그리고...

 

알고리즘 공부하자.

 

레이팅 변화 1643 - 29 = 1614

My Performance: ★★★☆☆