대회후기: Educational Codeforces Round 76 (Rated for Div. 2)

일주일만에 Codeforces에서 대회를 뛰었다.

대회 직전에 잠깐 잠을 자다가 못 일어날뻔 했다. 시작 10분 전에 일어나서 데스크탑을 켜고 대회 start.

---

A: Two Rival Students

1분 이내로 풀었어야 하는 쉬운 문제. 라이벌 두명을 이웃한 학생과 x번 swap해서 최대한 멀리 떨어뜨리는 문제이다.

그냥 거리를 x만큼 더 벌리면 된다.

하지만 문제를 잘못 읽어 이웃한 학생만 swap할 수 있다는 조건을 놓쳤다.

WA 추가 && 6분 낭비 후 AC

---

B: Magic Stick

주어진 두 operation의 특성을 보고, 일정 숫자 이상이면 모든 숫자를 만들 수 있음을 알아차리면 된다. 3 이하의 숫자로 시작할 때만 잘 처리하면 되는데, 경우를 예쁘게 나누지 못해 if else 코딩하느라 시간을 좀 버렸다.

12분: AC

---

C: Dominated Subarray

또 문제를 잘못 읽었다. 최소 크기의 dominated subarray를 찾아야 하는데, 혼자서 최대 크기라 착각하고 풀이를 만들었다. 문제를 다시 읽어보고 잘못 푼 것을 깨달은 후, 잠시 집중력이 흐려져 아무 생각을 못했다. 시간이 꽤 지난 후 증명 없이 떠올린 직관적 풀이로, 그냥 동일 숫자 사이의 거리 중 최솟값을 찾아서 이용하는 방법이 생각났다. (사실 처음에는 동일 숫자가 처음으로 다시 등장하는 위치를 찾았으나, 이는 최소 길이가 되지 않음을 금방 깨닫고 앞과 같이 수정하였다.) 한번 생각해 보니, 반복되는 숫자 간격의 최솟값을 찾았으니 그 두 숫자 사이에 다른 어떤 숫자가 두번 들어가 있을 수는 없을 것이다. 이에 구현을 하고 제출해서 AC.

29분: AC

---

D: Yet Another Monster Killing Problem

문제를 보는데 DP 느낌을 살짝 받았다. 앞부터 몬스터를 잡으면서, 한번에 최대한 많은 수의 몬스터를 잡을 수 있는 hero를 효율적으로 찾는 방법이 필요했다. 그리고는 아무 생각이 들지 않는다. 그리고 아무 생각이 들지 않는다. 그리고...

결국 아무것도 안하고 있을 수는 없어서 그냥 naive하게 앞부터 최대한 많은 몬스터를 잡는 hero를 하나씩 돌면서 찾는 코드를 작성했다. 복잡도는 정확하게는 계산하기 힘들지만 \(O(NM)\)이었을 것 같다. 제출해봤더니 RTE가 뜬다. 망할 파이썬...

이렇게 한시간이 더 지나고, 갑자기 hero중 redundant한 녀셕들을 지울 수 있겠다는 생각이 들었다. 바로 구현했지만, 이후에 뭘 해야할지는 다시 모르겠다. 그래서 그냥 앞에서 쓴 방식으로 다시 한번 구현해봤다. 이번에도 \(O(NM)\)이었을 것이다. 다시 RTE. 고쳐서 WA. 또 고쳐서 놀랍게도 AC. 이게 왜 통과하지???

1시간 54분에 AC, 해킹 위험 높음

이후에 Nyso가 이용한 풀이를 보니, 역시 전처리를 잘 해서 그리디하게 \(O(N + M)\)으로 처리했다. Power가 아닌 endurance 기준으로 풀이 생각을 했어야 하는데, 나는 접근의 방향이 잘못되었었다.

결국 HACKED

---

총평

무려 두 문제나 잘못 읽었고, 구현도 자꾸 꼬이는 날이었다. 이렇게 시간을 많이 버리고 시작했는데 D마져 빠르게 해결하지 못했다. 오늘은 몰라서 못 푼 문제는 없었다. 오늘의 대회로부터 얻어갈 교훈은 문제를 제대로 읽어야 한다는 것이다. 바로 코드를 짜는 것보다 머리로 한번 더 생각하는 태도가 필요할 것 같다. D의 경우, 좀 더 다방면으로 생각을 펼쳤어야 한다. 문제의 해결책이 보이지 않는다면, 당황해하지 말고 각도를 바꾸어 접근해보자. 오늘같은 대회의 A~D는 한시간 이내로 풀어냈어야 한다.

 

레이팅 변화 1671 - 28 = 1643

My Performance: ★★☆☆☆