UCPC 2020 후기

팀 구성

---

 

 

 

ICPC 팀 구성은 작년 12월에 했고 그 팀 그대로 UCPC에 참가했다.

 

평소에 팀원들끼리 ICPC 문제 셋을 풀어보거나 새로운 알고리즘 공부를 꾸준히 해왔는데 팀 연습은 전혀 안하고 있었고 마침 UCPC가 좋은 팀 연습 기회가 될 것이라 생각했다.

 

UCPC 본선 진출을 목표로 참여했고 본선에 진출하면 우리팀이 어느정도의 실력인지 확인하고 싶었다.

 

올해 UCPC는 모두 온라인으로 진행되었다. 오프라인으로 진행됐으면 더 재밌었을텐데 조금 아쉽다.

 

 

 

 

 

예선 전

---

 

원래 ICPC 셋을 하나 잡아서 계속 풀어보고 있었는데 UCPC를 대비해서 예선 전 2주동안은 18/19년 예선 기출을 풀어봤다. 못 푸는 문제도 문제의 풀이, solved.ac 랭크, 스코어 보드를 보면서 난이도를 파악하고 어느정도의 수준의 문제를 풀어야 본선을 가는지 가늠했다.

 

19년 예선 문제가 전반적으로 정말 좋은 셋이었다.

 

재밌게 푼 문제는 대회, 별다줄, 공교육 도박

위 문제 중에서 트라이를 한 번도 안써봤는데 트라이를 써야만 문제 제한 내로 딱 풀리는 문제를 처음으로 봤고 그렇게 처음으로 트라이를 구현해서 풀어봤다. 생각보다 어려웠다.

 

유령의 집은 풀이는 보고 생각이 났는데 거울 반사 때문에 구현이 너무 복잡했고 생각한대로 구현했는데 어딘가 틀렸는지 틀렸습니다를 받았다. 디버깅하다가 포기했다.

 

반대로 제일 맘에 안들었던 문제는 교점 세기. 미적분 + case work다. ICPC 스타일도 아니고 재미도 없어보여서 건드리지도 않았다.

 

yonsweng이 풀이를 안보고 '별다줄', '공교육 도박'을 풀었는데 역시 대단하다고 생각했다. '대회'도 거의 풀어냈었다.

 

powergee는 '유령의 집', '소각로'(18년 기출)을 풀어냈는데 복잡한 구현을 함수화하면서 차근차근 잘 풀어내는 모습을 보였다.

 

 

팀원들이랑 18년 풀이를 확인하는데 우리 외에도 4명이 더 보고있었다

 

 

 

 

 

예선

---

 

7월 25일 오후 2시부터 5시까지 스터디룸을 예약해놨고 칠판에 AC 표를 그렸다.

 

다같이 긴장하고 1시가 되는걸 기다렸는데 대회 페이지가 안들어가졌고 페이스북 해커컵 예선 문제를 풀면서 기다리는데 아래와 같은 메일이 왔다.

 

트래픽 폭주로 백준 서버가 마비되었고 결국 대회를 연장하고 4솔브 이상은 모두 본선으로 진출하게 되었다.

2020년 7월 25일 서버 사고

 

문제를 확인한 시각이 4시였는데 스터디룸이 1시간 밖에 남아서 4솔브만 하고 바로 나왔다.

1시간동안 푼 문제는 다음과 같다.

A 수학은 비대면 강의입니다.

연립방정식의 해를 구하는 문제. x, y의 범위가 좁아서 브루트포스로 풀린다.

G 루머

문제 설명대로 루머가 퍼지는 조건이 성립되면 BFS처럼 퍼뜨리면 된다. 구현은 BFS가 아니라 위상정렬처럼 구현한다.

D ㄷㄷㄷㅈ

D-트리, G-트리를 세면 된다. G-트리는 단순하게 조합 공식으로 해결했고 D트리는 DFS로 부모마다 인접해있는 '자식이 1개인 노드'와 '자식이 0개인 노드'의 개수를 구해서 서로 곱했다. 더 쉽게 할 수 있는데 조금 복잡하게 풀었다.

H 사과 나무

2가지 조건을 체크하면 된다.

1. 남은 길이가 3으로 나누어 떨어지는지

2. 1을 채워야하는 횟수(= 홀수의 갯수)만큼 모두 물을 줄 수 있는지 

못 푼 문제 - J 역학 조사

두 팀원들은 예선 시간동안 고민했는데 해결하지 못했고

나는 대회 끝나고 고민해봤는데 결국 못 풀었다.

아직도 내 실패한 문제 현황에 남아있는데 언젠간 스스로 풀어낼 예정이다.

 

 

 

우리팀은 4문제를 풀어서 본선에 진출했고

원래 50팀 정도 진출하는 본선을 이번에는 약 170팀이 진출했다.

 

 

 

 

 

본선

---

8월 1일 오전 11시부터 오후 4시까지 5시간동안 진행되었다.

 

본선도 온라인이기 때문에 이번엔 AC 표를 Google 스프레드시트를 이용했고

 

대회 초반은 대화를 안하고 AC 표에 표시해서 서로의 풀고있는 상태를 확인했다.

 

초반 12문제는 아래와 같이 분담했다.

 

iknoom1107 : A B C D

powergee : E F G H

yonsweng : I J K L

~0시간 19분

A번 AC - iknoom1107

DFS로 풀리는게 보여서 바로 구현해서 풀었다.

첫번째 DFS로 도달해야하는지 체크하고 두번째 DFS로 거리를 계산했다.

더 빨리 풀 수도 있었는데 조금 늦었다. 나중에 보니까 두번째 DFS는 필요없었다.

다음에는 스코어보드에 C를 푼 사람이 많이 보여서 C를 풀었다.

~0시간 50분

C번 WA - iknoom1107

이 문제는 예제가 큰 힌트였다. row가 같으면 사이클인게 보였고 결국 사이클이거나 아닌 경우로 나눌 수 있었다.

1. 사이클이 아닌 노드 : 가리키는 노드가 사이클이면 사이클의 노드의 수를 정답에 곱한다.

2. 사이클 : 원순열의 갯수를 구한다.

문제를 짧게 생각하고 원순열이 아니라 2를 곱해버렸다가 1WA를 받았다.

~0시간 57분

C번 AC - iknoom1107

원순열로 곱해서 맞았다.

이 문제는 파이썬으로 풀면 간단해지는게 보였고 시간도 넉넉해서 파이썬으로 풀었다.

이후 나는 B를 읽었고 yonsweng은 L을 풀고 있었고 powergee는 G를 풀고 있었다.

~2시간 12분

L번 AC - yonsweng

4번의 WA 끝에 yonsweng이 L번을 맞췄다.

대회 끝나고 확인하니까 우리팀에서 AC한 문제 중에 제일 어려운 문제였다.

~2시간 20분

B번 AC - iknoom1107

3번 WA를 하고 AC를 받았다.

나는 전처리를 복잡하게 한 다음에 lower_bound, upper_bound를 사용했다.

풀이를 보니까 정해는 Two pointer를 사용하는데 오버킬을 했다.

C++ 코딩 속도가 느린데 lower_bound, upper_bound를 쓰기도 했고

정해보다 로직도 복잡하다보니 1시간 20분이나 걸리고 중간중간에 WA까지 받아버렸다.

 

 

이때까지 가장 많이 풀린 문제는 순서대로 D I G F였다.

 

G는 구현의 느낌이 나서 powergee가 읽고 초반부터 공략해봤으나

단순 구현 이상의 최적화가 필요했고 결국 포기했다.

 

F는 모두가 읽고 버렸다. 우리가 풀 수 있는 수준이 아니라고 판단했다.

 

yonsweng은 D를 풀고 나는 I를 읽었다.

powergee는 두 문제를 모두 읽고 풀이를 같이 의논했다.

~3시간 30분

I번은 원형이 아닌 경우 풀이를 생각해냈다.

하지만 이게 원형이면 어떻게 해야하지 한참 생각하다가 결국 포기했다.

풀릴 듯 말 듯 하다고 생각했는데 나중에 풀이를 보니 전혀 아니었다.

풀이가 생각이 안나면 일단 포기하고 많이 풀린 문제는 일단 읽어볼걸 조금 후회했다.

이때서야 팀원들과 D를 읽기 시작했다.

~4시간

D번도 만만치 않게 어려웠다.

처음에 문제를 조금 잘못읽었는데

모든 쌍의 거리의 제곱( (a + b + c + ...) ^ 2 )이 아니라 

모든 쌍의 거리를 구해야하고 거리가 제곱으로 정의되어있었다. (a ^ 2 + b ^ 2 + c ^ 2 + ...)

위로 문제를 잘못 읽고 gene tree처럼 풀어야하나 생각하고 조금 시간을 버렸다.

~5시간 (대회 종료)

문제를 제대로 읽고 그럴듯한 O(NM) DP 풀이를 생각해내고 구현을 시도했다.

하지만 생각해낸 풀이가 구현이 간단하지 않았고 실수까지 해버려서 결국 대회가 종료되었다.

 

 

 

 

최종 4 solve 패널티 508min으로 본선 대회를 마쳤고 최종 40등을 했다.

40등만으로도 나름 목표한 만큼의 등수를 얻었다고 생각하지만

역시 한 문제만 더 풀면 20 ~ 30위에 들 수 있었을텐데 하면서 조금 아쉬웠다.

아마 ICPC 리저널에 입상하려면 저기서 한 문제는 더 AC 할 정도의 실력을 갖춰야 할 것이라 생각했다.

 

 

 

 

소감

---

5시간은 긴 시간이 아니다.

 

쉬운 문제를 빠르게 풀어서 어려운 문제를 풀 시간을 확보하는 것도 필요하다. 하지만 어려운 문제의 풀이를 풀어낼만한 배경지식도 필요하기에 결국 어떤 문제든 많이 풀어봐야겠다고 생각했다. solved.ac 기준 gold3 ~ platinum4를 막힘 없이 빠르게 풀어내고 platinum3 ~ diamond5 정도의 어려운 문제를 맞춰야 대회에서 입상할 수 있을 것이라 체감했다.

 

난 A, B, C를 푸는데 2시간 20분이 걸렸는데 정해를 잘 생각해내고 실수를 안하고 구현속도가 더 빨랐다면 1시간 내로 풀 수 있었을 것이라고 생각한다. 일단 그 부분이 아쉬웠다.

 

처음부터 G번 같이 어려운 구현 문제를 붙잡아서 풀어버리는건 좋은 전략이었다고 생각하지만 실제로는 구현 이상으로 효율적으로 처리하기 위한 로직이 필요했고 그래서 아쉽게도 실패했다.

 

구현/파싱과 같은 문제가 아니면 위와 같은 전략은 좋지 않다고 생각한다. 읽고 바로 풀이가 생각이 나지 않으면 많이 풀린 순으로 먼저 읽어봤어야했고 나는 I번을 너무 오래 붙잡고 있어서 결국 상대적으로 쉬웠던 D에 시간을 투자하지 못했다. 이것도 아쉬웠다. 5시간은 긴 시간이 아니기에 판단을 잘 했어야했다.

 

UCPC 덕분에 이러한 팀 경험을 할 수 있었고 우리팀의 수준도 확인할 수 있었다.

 

대회를 운영하느라 여러모로 고생한 전대프연에 감사했다.

 

 

 

 

 

 

 

끝!