Day 113. SUAPC 2023 Winter 후기 (as :blobdundundun: of :blobsad:)

지금 이 문장을 입력하는 시간은 2월 26일 오전 11시 45분.

오픈콘이 종료된 2월 26일 늦은 저녁에야 공개가 가능할 후기를 미리 쓴다.

 

포스터. 간지난다.

 

코딩 113일차.

이것저것 배우자는 의미로 신청한 모르고리즘에 덜컥 붙어버렸다. 전통이 깊은 12년차 동아리에 이런 쩌리가 들어가도 되나, 들어가고 나서도 매일 기대 반 걱정 반이었다. 이상한 별명(수학좌)를 얻고 모르는 문제 물어보고... 그래도 동아리에 들어가니 뭔가 다르긴 다르구나 하는 생각이 들던 찰나, SUAPC 2023 Winter 공지가 떴다.

처음에는 재혁씨가 스카우트 하려고 했었다. 나 따위를?

오렌지, 퍼플, 그리고 그레이?

당연히 고사했다. 백준에서 플레 찍긴 했지만 그게 수학 원툴이었고, BFS니 DFS니 백트래킹이니 하는 기초적인 것도 모르는 상황이라 수락하기에는 양심이 매우 많이 찔렸다.

내가 고사한 저 팀이 내가만든쿠키 팀이 되었고, 추후 2등 상을 받게 되었다. 저 팀에 들어간다고? 어림도 없는 소리. 난 본분을 아는 사람이다.

그리고 휘주씨가 톡을 주어 영입했고. 그렇게 팀이 정해졌다. 그 때도 고사하려고 했지만 실력 비슷하다고 같이 하자고 하셔서... 물론 지금 다시 생각해 봐도 세 명 중 가장 코딩 못 하는 사람은 여전히 나다.

프리즈 전 스코어보드

최종 스코어보드 (대회 후 스트리밍 캡쳐)

팀원을 잘 만난 터라 혼자서는 못 풀 문제를 여럿이서 같이 푼다는 경험을 했고, 그게 생각보다 매우 재미있는 일임을 알았다. 팀 연습 때도 비슷한 느낌을 받았지만, 모두가 놓치던 반례를 한 시간을 끙끙대며 찾아 헤메다가 드디어 찾았을 때. 그리고 그 반례를 토대 삼아 수정한 코드가 정답을 이끌어낼 때의 희열은 철저한 개인전인 PS에서 느끼기 힘든 감정 중 하나다.

가능하다면, 이런 팀업 대회가 상설화되기를 바랄 따름이다. BOJ에서 주관하는 개인 대회에서도 팀업 대회가 생기기를 바라는 감이 있다. Google CodeJam이 사라지며 구글 코드 노잼이 되는 이 시기에 과연 바래도 되는 사안인지는 모르겠다만.

 

:blobsad: 팀은 :blobdead:(ez_code), :blobglitch:(parkhwijoo), :blobdundundun:(나)로 구성되었다.

우리 팀은 수상보다는 6솔을 노리던 팀이었다. 이전 SUAPC 모두 골드 이하의 문제가 6개였고, 팀연습 때 SWERC 2019 셋을 받아서 골드 이하는 전부 풀어낸 전적이 있기에 그렇게 마음을 잡았다.

뚜껑을 까 보니 6솔이 수상권이었고 골드 이하가 몇 개 없었다는 게 흠이지만. 이래서 지난 수능 보고 다음 수능 난이도를 추산하면 안 된다고 하는구나.

 

우리 팀 :blobsad:가 푼 문제는 A, F, K, M의 네 문제이다.

대회 시작 전 앞에서부터 4문제씩 끊어서 :blobdead:, 나, :blobglitch:가 보기로 했다. M은 전부 다 보고 시간 남는 사람이 도전하는 것으로 전략을 짰고.

그런데 E, G, H는 나의 힘과 실력으로는 풀기는 커녕 감마저도 잡을 수 없는 문제들이었다. E는 런타임 전의 전처리가 답일 거라고 생각했고(사실 재귀였다), G는 게임 이론 + 트리라서 알지도 못하는 종류. H는 lattice의 유시 convex hull이라고 생각했다. 전부 걸렀다.

 

A는 거저 주는 문제라 내가 보기도 전에 구현이 끝나 있었다. 가장 쉬운 문제. 코딩 짬이 100일을 넘어가는데 이 정도는 풀어야지.

F는 naive로 터질 것 같다(=Python당해서 시간 초과 날 것 같다)는 이상한 상상을 해서 :blobdead:에게 검토해 달라고 부탁했다. 문제는 내가 생각한 naive가 각 구간별로 판단하는 방식이었다는 것이다. 그게 정해였고. 개 쓸데없는 짓을 해서 시간을 날려먹은 셈. 이번 대회에서 한 두 가지 후회 중 하나가 바로 F에 겁먹은 것이다.

ㅜ

K는 시작하자마자 눈여겨봤다면 내가 퍼솔을 먹지 않았을까 하는 후회가 있다. 이상한 L번 문제에 말려서 대회 초반 2시간 동안 다른 문제는 거의 보지도 않았다. 네 문제 중 내가 구현을 맡은 유일한 문제이다. R이 주기가 720이고 시계가 1500개라서 브루트포스로 풀면 되나? ← 이게 되더라.

M의 아이디어는 내가 냈고, 구현은 :blobdead:가 맡았고, 몇 번 말리면서 60분동안 찾던 반례를 :blobglitch:가 찾았다. 이것저것 써 보며 찾던 반례가 눈 앞에 있었다는 걸 깨닫고 허탈하긴 했지만, 그 반례 예외처리만 했더니 코드가 통과하더라.

 

못 푼 문제 썰도 좀 풀어보자면...

L은 비교차 경로계와 유사한 문제라 판단했다. 비교차 경로계에는 유명한 공식 Lindström-Gessel-Viennot Lemma이 있다. 아니면 Young Tableau로 치환해서 생각해 보던가. 이 문제의 정해는 어느 쪽이든 관련된 closed form이 있을 것이라고 확신을 했다. 인터넷에서 논문을 보고 그 closed form을 찾아서 구현만 하면 맞힐 수 있을지도 모른다고 생각을 했고... 그렇게 2시간을 날려먹었다. 짬짬이 다른 문제도 보긴 했지만.

E는 permutation group 관련한 문제라고 생각했다. 내가 수학을 알아서 모든 걸 수학으로 치환하여 생각하는 버릇이 있다. 나쁜 버릇이긴 하다. 그래프 연결 모양이 거지같아져서 포기했지만, 이걸 linear하게 펴는 테크닉만 생각했으면 어쩌면... 트라이는 할 수 있지 않았을까? trie 말고.

J는 connected component에 가중치를 가진 MST가 되지 않을까 하고 생각했다. 대회 막바지에 이거 정도는 도전해 보자 하면서 이것저것 아이디어를 냈고, 그래프 이론 관련된 문제라는 것 하나만 알아차렸다. 나는 이게 loop를 제외하면 단순그래프가 될 것이고, 결과적으로는 forest 비슷하게 될 것이라고 강력하게 주장했는데, 어처구니없게도 틀린 직관이었다.

 

대회 끝나고 스코어보드 까기 전 실시간 스트리밍을 보면서 출제자들의 '내가 알면 웰노운' 해설을 보며 속으로 많이 욕했다.

미안해요 출제진! 하지만 H번이 어딜 봐서 골드입니까? 이건 님들이 잘못했어요. 그런 것으로 합시다.

 

스코어보드 까면서 연세대 팀이 계속 위로 올라가는 거 보고 동아리방에 모여서 환호했다. 전전 회장님인 lky7674님이 스코어보드 보고 흡족해 할 거라는 생각을 했다. 당연히. Top3를 모두 연세대가 먹었으니!

전체 42팀 중 15등에 연세대학교에서는 10팀 중 6위를 했지만, 우리 팀 위의 다섯 팀이 1등 2등 3등 9등 10등으로 모조리 수상권에 들어버린 바람에 우리 팀이 학교별 특별상을 받게 되었다. 수상권에 들지 않은 팀 중 교내 1위라는 조건을 만족시킨 탓이다. 이것도 상은 상이니 매우 만족한다. 상위 50% 안엔 들었잖는가 그리고.

---

여담

1. 10등컷 팀이 프리즈 시점에서 닉값을 하는 바람에 스코어보드 까는 중에도 위로 올라가나 마나 하는 기대 많이 했다.

2. 10만원감사합니다 팀은 프리즈 시점에서 닉값을 하지 못했는데, 제출 문제가 G, H, J, M인 거 보고 무난하게 상금 타 가겠거니 생각했다. 그 쪽 팀원분들하고 콩불에서 출제진 뒷담(?)을 좀 깠다.

3. 마지막 제출 특별상을 노리고 절대 못 풀 문제에 제출을 하려고 했는데, 타임네이비즘까지 켜 놓고도 실패했다. 수강신청이 선착순이었으면 내 시간표는 분명 거적때기가 될 것 같다.

4. 두 팀원이 허락한다면 Summer SUAPC나 PS연고전도 이 팀으로 나가고 싶다. 내가 제 역할을 했는지는 모르겠는데...

5. 일단 기본적인 테크닉부터 배워야 할 것 같다. DFS BFS를 모르는 건 말이 안 되지 않을까? 싶기도 하고. 언제까지나 뉴비로 남아 있고 싶지도 않고.

6. 다른 팀들의 후기도 어서 보고 싶다. 다른 팀들이 내 후기도 봐 줬으면 좋겠고.

7. 언젠가는, 정말 언젠가는 이런 대회에 출제도 한 번 해 보고 싶다. 창고에 몇 문제 쌓여 있긴 하다.