SUAPC 2020 Div.1 참가 후기

SUAPC (신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회) 2020 Div.1에 참가하였다. 

 

팀명 : 처음보는사람들끼리신청마감1시간전에만든팀

팀원 : pjh6792(나) , dart , seastar105

 

신촌지역의 대학교(연세대, 서강대, 홍대, 이대, 숙대)들이 연합해서 개최한 대회이며, div1에는 총 29팀이 참여했다고 한다.

 

본격적으로 알고리즘을 공부한 지 약 4달째만에 처음으로 실전 대회를 참여하게 되었는데, 정말 열악한 환경 속에서 참가했다. 

 

우선, 3명 다 모두 초면이었고 대회 신청 마감 직전에 팀을 모아서 신청하게 되었다. (팀 이름의 유래다...)

사실 원래는 어차피 서울에도 가지 못하고, 개인적인 테스트 겸 대회를 참가하려 해서 1 인팀으로 신청을 했었다. 물론 다들 ICPC를 준비하는 팀 그대로 이 대회를 출전해서 팀원을 구하기도 어려웠다. 그러다가 신청 마감날에 팀원을 구한다는 slack 알림을 보고 바로 DM을 보내서 온라인으로도 괜찮은지 여쭤봤고, 괜찮다는 답변과 함께 바로 팀을 결성하게 되었다. 

 

이렇게 팀을 결성하다 보니, 내가 서울에 가지 못하는 상황이라서 구글밋을 이용하여 마이크로 대화하며 진행해야 했다. 대회 이전에 2번의 팀 연습을 했는데, 그땐 사실 한글 문제 셋을 찾느라 비교적 쉬운 셋들만 풀어서 크게 막 서로의 코드를 보면서 디버깅하고 설명해주고 할 기회가 적었는데, 막상 어려운 문제를 접하다 보니 온라인의 한계가 절실히 느껴졌다. 물론 나를 제외한 두 팀원은 만나서 했기 때문에 서로 의견을 자유롭게 나눌 수 있었지만, 사실상 세명이 함께 코드를 보며 문제를 해결하기는 불가능했다. 

 

셋이서 함께 문제를 풀어나가기보단 셋이서 문제를 나눠 풀었다는 게 더 적절한 표현이지 않을까......

 

그래도 우여곡절 끝에 동상(5등)을 차지하게 되었다...!  

 

(대회 도중에 1등 팀을 보고 미쳤다고 생각했는데 알고 보니 월파팀이라고 하더라,,,,)

 

 

문제 : https://www.acmicpc.net/category/detail/2274

해설 : https://www.acmicpc.net/board/view/55167

 

 

우리 팀은 dart님이 3k+1번째 문제, seastar105님이 3k+2번째 문제, 내가 3k번째 문제를 읽었다.

각자 15분 내에 문제를 다 읽는 것을 목표로 하였다. 

 

---

 

- A번 [200년간 폐관수련했더니 PS 최강자가 된 건에 대하여]

 

개인적으로 제일 아쉬웠던 문제였다. 

스코어보드를 보면 거의 대부분 A번을 풀었는데, 우리 팀만 A를 해결하지 못했다. 

심지어 1솔브한 팀들도 거의 A번을 풀었다. 

 

처음에 내가 맡은 문제를 보고 나서 A번을 봤을 때, dp 느낌이 나서 잠깐 생각해봤는데 아이디어가 잘 떠오르지 않아서 조금 어려운 문제일 것 같았는데, 점점 스코어보드에서 채워지는 A번을 보고 쉬운 문제였다는 걸 알게 되었다...

괜히 복잡하게 생각했다가 낭패를 봤다. 후에 팀원이 마지막 1시간 정도를 A에 투자했지만 결국 해결하지 못했다. 

역시 기본기가 아직 부족한 것 같다...

 

 

- B번 [꿀벌]

 

이 문제는 뭐.... 보자마자 못 풀 것 같았다. 처음에 seastar105님이 풀어볼 만할 것 같다고 해서 읽어보았는데, 방법이 전혀 떠오르지 않았다. 대회가 끝나고 나니 출제자 피셜 B가 제일 어려운 문제였다고 하는데 역시나. 괜히 시도했다가 큰일 날뻔했다.

 

 

- C번 [케이크 커팅]

 

내가 제일 처음 읽은 문제이다. 창을 열자마자 기하문제라는 걸 알았고, 읽어보니 입체도형에 중간중간 뚫려있고... 바로 패스했다. 역시나 어김없이 다이아 문제.

 

 

- D번 [가뭄(Large)]

 

유일하게 지문조차 이해가 잘 안 된 문제다. 문제에서 구하는 게 뭐지? 생각이 들자마자 바로 패스. 이것 또한 다이아 문제

 

 

- E번 [독특한 계산기]

 

내가 이 문제를 읽기도 전에 seastar105님이 해결해서 무슨 문제인지도 몰랐다. (물론 아직도 읽어보지는 않았다...)

출제자 피셜 E번이 가장 쉽다고 판단했다는데, 개인적으로는 I가 제일 쉬운 문제인 줄 알았다.  

 

 

- F번 [울타리]

 

내가 두 번째로 읽은 문제이다. 문제를 읽자마자 '가장 먼 두 점의 거리' 문제가 떠올랐고, 로테이팅 캘리퍼스 알고리즘이 생각났지만 구현은 할 줄 몰라 팀원들에게 혹시 아는 사람이 있는지 물어봤는데 아무도 없었다. 나 또한 이름만 알기 때문에 그냥 바로 넘겼다. 대회가 끝나고 다이아 4가 찍혀있는 걸 보면 이 또한 잘 넘겼다고 생각한다...

 

 

- G번 [마스크가 필요해]

 

대회 마지막에 내가 30~40분 정도를 쏟아부은 문제이다. 결국 해결하지는 못했다. 

기존에 유명한 문제인 '회의실 배정' 문제와 비슷한 느낌이 들어, 그리디 측면에서 접근을 했는데 결국 대회 종료까지 예제 입력도 해결을 못했다. 그렇게 어려운 문제로는 안 보였는데 이 문제를 조금 더 일찍 시도했으면 어떨까 하는 생각이 든다. 

 

 

- H번 [전설]

 

동상을 받을 수 있게 만들어준 문제다. 팀원인 seastar105님이 해결했다. 처음 seastar105님이 문자열 해싱을 해본 사람이 있냐고 물어본 뒤, 아무도 없어서 포기하려나 싶었는데 나를 제외한 두 분이서 잠깐 토의를 해본 후 시도해서 프리징이 된 후에 기적처럼 AC를 받았다. 사실 나는 이 문제를 풀고 있는지도 몰랐다...(온라인 참여의 단점을 제대로 느꼈다)

프리징이 된 상황에서 우리 팀이 2 솔브로 5등이었지만, 그 밑에 2 솔브가 몇 팀이 있었기 때문에 3 솔브가 아니면 수상권이 힘들겠다고 생각했는데 다행히 해결했다. 

그동안 문자열에 대한 공부를 전혀 안 해왔는데, 슬슬 공부를 해봐야겠다.

 

 

- I번 [수학은 재밌어]

 

내가 푼 문제이고 퍼솔이었다..! 

여러 가지 운(?)이 겹쳤던 것도 있고, 이 문제를 빠르게 풀어서 시간적인 측면에서도 많이 이득을 봐서 3 솔 중에 1등을 하는데 조금이나마 영향을 주지 않았나 싶다. 

일단, 내가 C, F, I 순으로 문제를 보는데 하필 C, F가 모두 기하 문제였다. 그래서 앞의 문제를 빠르게 넘겨서 I를 초반에 볼 수 있었고, 또 대회일 불과 1주일 전에 신촌 연합 여름 캠프 '정수론' 강의를 들어서 오일러-토션트 함수의 구현 방법을 알고 있었다. 코드 또한 미리 작성해둔 게 있어서 문제를 읽고 바로 가져다 놓았다. 

그다음 문제를 읽어보니 n의 범위가 생각보다 크지 않았고, x*phi(x)이므로 이 값이 n보다 커지는 x가 어느 부분일까 생각을 해보다가 x가 2의 거듭제곱인 경우에 phi(x)가 제일 작아진다고 생각을 했었다.

물론 이 풀이는 틀린 풀이이다. x를 소인수분해를 했을 때 소수가 다양할수록 서로소의 개수가 작아지기 때문에 대충 

4*3*5*7*11*13 정도가 x*phi(x) > n을 만족하는 작은 x가 될 것이다. 다행히 이 값이 2^16과 비슷한 값이었다. 

대회 때는 x에 2^15, 2^16, 2^17등을 직접 넣어보면서 phi(x) 값을 구해보고, 2^16부터 만족하길래 바로 x의 범위를 1 ~ 2^16으로 잡았고, 그 범위 안에서 만족하는 x가 없으면 -1을 출력하는 방식을 이용했는데 AC를 받았다. 

 

*후에 다시 대입해보니 시간 안에 x = 1000000까지는 아슬하게 통과를 한다. 

 

 

- J번 [상품권 준비] 

 

내가 맡은 문제(C, F, I, L)를 다 읽고 잠깐 방황하다가 J를 잡고 풀었다. 개인적으로 1시간은 쏟아부은 것 같은데, 왜 안 풀렸는지는 잘 모르겠다... prefix xor을 이용하였고, 팀원의 수가 정해져 있기 때문에 그 수만큼의 길이를 갖는 구간들을 각각 구하고 뭐 어찌어찌해서 직접 만든 예제까지 다 돌렸는데. 아쉬움이 많이 남았다. 

퍼솔한 팀이 되게 빨리 풀어서 쉬운 문제일 것이라 생각했는데 그 팀이 월파팀일 줄은,,,,

 

 

- K번 [물건 가져가기]

 

아직 무슨 문제인지 모른다. 난이도를 보니 다이아인걸 보아 아마 당분간 계속 모를 예정이다.

 

 

- L번 [카드 셔플]

 

처음에 잠깐 seg tree를 생각했다가 아닌 것을 금방 깨닫고 패스했다. 

 

---

첫 실전 대회였는데, 나름 긴장도 되고 재밌었다. 무엇보다도 이 대회를 통해서 느낀 점과 얻어가는 점이 있다는 것에 매우 다행이라고 생각한다. 

비록 아직 실력은 많이 부족하지만 내가 지금 알고리즘을 공부해나가고 있는 과정이 크게 틀리지는 않았다는 생각이 들었다. 내가 아는 알고리즘이라면 문제를 봤을 때 그 알고리즘이 떠오른다는 것 자체가 나름 발전한 것이 아닐까..? 물론 아는 알고리즘이 많지는 않다는 게 조금 문제긴 하다. 

그리고 그동안 내 실력을 가늠할 수 있는 게 사실 코드포스 레이팅밖에 없었고 그 레이팅 조차 점수가 잘 오르지 않아 회의감이 많이 들었었는데, 확실히 코포랑 이런 프로그래밍 대회랑은 차이가 꽤 나는 걸 느꼈다. 

하지만 그래도 잘하는 사람들 중에 코포 레이팅이 낮은 사람은 없으니.... 너무 합리화하지 말고 계속 노력해야겠다.