Day 352. 2023 ICPC Korea Regional Online Competition 후기

ICPC 온라인 예선이 끝났다. 본선 진출인지 아닌지는 아직 확실하지 않지만, 그래도 프리즈 전 스코어보드만 따지면 나름 합격점을 주고 싶다. 나름 잘 했다. 정말로. 결과만은...

오히려 내가 본선 진출 가능성에 불확정성을 집어넣어 줘서 미안하기 그지없다. 팀원 중 한 명은 내년이 졸업이라 이번이 마지막 ICPC라는데, 이 사람이 하필 나와 엮여서 올라갈 수 있음에도 온라인 예선에서 ICPC를 마무리짓게 된다면 정말 미안해서 고개를 들 수 없을 것 같다. 제발, 본선만 진출할 수 있게 해 주세요.

프리즈 시점 스코어보드

프리즈 해제 스코어보드

우리 팀이 푼 문제는 C, D, G, K이다. 프리즈 시점 파란색 배경은 스코어보드 프리즈가 풀리지 않은 pending인데, 다섯 번을 박아넣었음에도 불구하고 정답을 따내지 못했다(:blobsob:). 나중에 저 문제를 푼 다른 팀에게 물어보니 90%의 풀이는 짰으나 걸러야 할 것을 거르지 못해서 아쉽게 못 맞췄던 것 같은데... 문제가 올라오기만 한다면 그 때 구현한 걸 바탕으로 조금씩 고쳐봐야겠다.

연세대에서는 8팀이 나갔다. 학교 내에서 4등이 되었다. 학교 안에서도 밖에서도 4솔은 많았는데, C D K를 상당히 빨리 풀어내서 4솔 중 페널티 관리가 굉장히 잘 된 편이었다. 덕분에 학내 4등, 전체 51등이라는 호성적을 가져올 수 있었고. 학교 내에서 상위 50% 조건을 맞춰야 본선 진출이 가능한데, 해당 조건은 이미 충족시킨 것 같다. 이제 24일 오후 5시에 발표되는 결과만 기다리면 된다. 부디 낭보이기를...

 

1. 팀 결성

ICPC를 나가고는 싶었다. SUAPC도, UCPC도 나갔으니 마지막으로는 ICPC로 한 해를 마무리짓고 싶었기 때문. 그러나 저번 SUAPC로 맺어진 팀에서 이미 다른 두 사람이 팀원을 구했다. 이것이 아싸의 숙명. 실력 비슷한 이들끼리 매칭을 해서 ICPC에 나갈 수 있도록 동아리에서 지원을 해 줬다.

그렇게 평소에 합을 안 맞춰 본 세 사람의 팀이 결성되었으나... 나중에 다시 이야기하겠지만 의사소통의 삐걱거림은 거의 없었다. 이게 바로 운명의 팀...? (아니다)

팀원은 본명의 가나다 순으로... nflight(나), qttw456, now_cow의 3인 팀. 팀원들을 소개하자면, now_cow는 (팀 결성 당시) 유일한 solved.ac 다이아몬드기도 하고, 또 유일한 C++ 주력이라 어려운 문제나 Python3으로 TLE당할 문제들의 구현을 맡는 역할이다. 이른바 버스기사. qttw456은 아이디어가 정말 좋다. 제시한 아이디어를 어느 정도 정리만 해 주면 정답으로 가는 길이 열린다. 이걸 어떻게 풀어야 할지 방향을 제시하는 길잡이 역할이라고 하면 될 것 같다. 게다가 손테케 생성도 정말 빨라서, 3인 1컴 체제인 ICPC에서 한 사람이 구현을 하는 동안 나머지 둘이 디버깅을 하는 게 가능했던 것은 모두 qttw456 덕분이었다.

그럼 나는 뭘 잘하냐... 타자가 빠르다... 파이썬으로 간단한 문제의 빠른 구현은 잘 한다. 그냥 양학용이지, 실력에 맞는 문제를 푸는 데는 그 능력이 빛을 완전히 잃어버린다. 그거 말고는... 수학에 그나마 강한 편이다. 지난 팀 연습 때는 그 강점이 빛을 조금 발할 수는 있었는데 이번 온라인 예선에서는 그 수학깡?패가 그다지 도움이 안 되는 특성이었다. 수학 문제는 지옥의 구현(E) 하나밖에 보이지 않았어서...

 

2. 10/7 팀연습 - NWERC 2014 (Regional)

2014 NWERC 리저널. 사실상 6솔(ㅋㅋ)

ICPC를 위한 대비책은 동아리에서 마련해 줬다. 9/30과 10/7 두 번의 기회가 있었는데 하필 9/30이 추석 연휴에 끼어 있어서 팀연습은 후자만 참가했다. 팀연습 참가 이전에 극한의 랭작으로 레이팅을 갈고닦아 solved.ac 다이아몬드까지 티어를 끌어올렸다. PS 실력과 1도 상관 없다고? 그거야 당연한 소리긴 한데... 그냥 기분이 좋잖아요 ㅋㅋ

서강대학교 원정으로 팀연습을 치뤘고... 또 뭐가 있었지? 팀연습 끝난 지 거의 2주가 다 지나서 과정은 대충 기억이 안 나지만, 제출 기록을 보고 대충 기억을 더듬으면서 타임라인을 작성해 본다.

앞에서부터 4 / 4 / 3으로 나눠서 now_cow, 나, qttw456이 가져갔을 것이다. 아마도... 참고로 now_cow와는 여기서 얼굴을 처음 봤다.

00:15 E AC

일단 문제지를 나눠받고 대충 보니 웬걸? 답이 바로 보이는 문제가 하나 있었다. c에 대한 순증가함수 하나와 순감소함수 하나가 주어져 있고, 그 함수 합이 최소가 될 때의 c와 그 때의 최솟값을 출력해 주는 문제였다.

두 함수의 합이 절대로 단조함수가 아니라는 믿음 하에 답은 golden section search였고, 이거는 내가 풀 수 있는 문제라고 단정하고 코드를 써내려가기 시작했다. 어렵지 않게 AC를 따낼 수 있었다. Golden section search가 생각이 안 나서 조금 더 메모리를 많이 먹지만 구현은 빠른 삼분 탐색으로 선회했고, 그 탓에 2~3분정도 더 소모했으나 팀연습 참가자 중에서는 가장 먼저 풀어낼 수 있었다.

저걸 어떻게 보자마자 바로 떠올렸냐면, 바로 직전 학기에 들은 수치해석에서 저걸 가르쳤기 때문이다. 다른 거 이것저것 많이 배웠는데 PS에 가장 유용하게 써먹을 게 이거라서 기억에 깊게 남을 수 밖에... 그렇기 때문에 여러분은 수학 복수전공을 해야 합니다(아니다).

00:26 J AC

다음은 간단한 set 문제였는데, 이런 쪽은 C++보다는 파이썬이 빠르다고 판단했는지 문제 설명을 듣고 구현은 내가 했다. 여기서 틀리면 솔브닥 다이아를 반납해야 한다.

01:46 F AC (+6)

now_cow가 C에서 지옥의 dp와 씨름하던 동안 F를 잡고 있던 내가 20% 이상이라는 것에 착안하여, 이 문제가 어쩌면 무작위화 문제가 아닐까라는 발상을 떠올렸다. 다른 문제 열심히 보고 있던 qttw456이랑 이야기하면서 이게 만약 possible의 케이스라면, 임의의 두 점을 골랐을 때 최악의 경우 0.04의 확률로 같은 직선 위에 있을 테니 한 100번 정도 굴려 보면 정답을 오답으로 잘못 판단할 확률이 대략 1.7% 정도가 될 것이라고 생각했다.

납득시킨 후 C에서 기진한 now_cow와 교대해서 열심히 구현했는데, 순식간에 세 번이나 페널티를 쌓고는 물러나고 말았다. 여기서 내가 오늘의 블랙홀이 되었는데요...

now_cow가 다시 C dp식을 수정하고 다듬는 동안 100번 정도 굴려보면 ← 여기서 100을 수정한 코드를 세 번 더 냈다가 오답만 적립했다. 대체 뭐가 문제일지, 트라이 수로 이분탐색을 하는 건 아닐지 농담따먹기를 하다가 갑자기 뭐 하나가 생각났다. 모듈화를 하면 조금 더 빨라진다는 소리를 어디선가 들은 기억이 있었고, 그제서야 그걸 써먹을 생각을 한 것이다.

에이 설마... 하면서 그것만 수정한 코드를 제출했더니 정답이더라. 팀원들이 너무 착해서 헛짓거리를 하면서 시간을 허비한 나를 따듯하게 보듬어 주었다. 평소에 혼자서 대회 할 때는 정말로 패널티 관리를 잘 하는 편이었는데 아무래도 긴장을 많이 했는가...

02:50 D AC (+5)

이제 문제 셋에서 수학은 찾아볼 수가 없게 되었고, 아주 자연스럽게 수학 원툴(?)인 나는 짐덩어리가 되었다. 이 쪽은 위상정렬 문제였는데, 나는 위상정렬 문제를 이 이전까지 단 한 문제도 풀어본 적이 없었다. now_cow와 qttw456이 뭔가를 만들어 가는 동안 나는 뒤에서 고개만 끄덕이고 있었다... 아니면 C dp 식을 검증하던가, 그것도 안 되면 A를 검증하고 있었다. 다이아 1인데 풀 수 있다고 착각해서 개뻘짓만 했던 기억이 새록새록...

그러면서 시행착오를 거쳐 둘이서 정답을 따냈다. 역시 민트. 무섭다...

04:26 C AC (+6)

이제 풀 만한 남은 문제는 C와 H, I 세 개로 좁혀졌다. I는 반으로 나눠서 어떻게 하면 풀리지 않을까 입으로만 전략을 세우고 코딩하는 법을 전혀 떠올리지 못했다. H는 내가 문제 해석을 해서 qttw456과 어떻게 하면 될 것이라 계속 도전은 하고 있었으나 계속 전진하다 멈추다를 반복하고 있었고...

그리고 큰 진전 없이 약 한 시간 반을 소모하다가 계속 틀리던 C에서 결국 now_cow가 dp식을 완성시켜 AC를 받고 돌아왔다. 순간적으로 후광이 보였다(ㅋㅋ)

TLE H AC (+4)

참고로 H는 끝나기 직전에 코드를 제출했는데 정말 미세한 차이로 코포 Gym이 먼저 끝났다. 그 코드를 개인적으로 제출했더니 바로 AC가 뜬 걸 보면, 중간에 시간만 조금 덜 낭비했어도 6솔이 가능하지 않았을까?

사실상 6솔이었고, 이 정도면 본선도 어렵지 않게 가능할 거라는 기쁨에... ICPC 대비를 상대적으로 소홀히 했다. ICPC 며칠 전에 원래 조금 알던 CRT, 이분매칭과 아직 모르던 위상정렬 공부를 조금 했고, 그리고 업다운 랜디를 조금 하면서 시간을 보냈다. 후술하겠지만, 중간고사 일정이 정말 환장하도록 ICPC에 불리했다.

변명이지, 쩝...

 

3. 일정 테트리스, 그리고 예비소집

발악

팀연습 직후 시험 일정이 정해지기 시작했다. 이번 학기에 무려 7과목 19학점에 3학점짜리 하나를 청강, 모두 전공과목으로 박아버린 터라 시험 일정도 지옥이 따로 없었다. 운 좋게 한 과목은 시험이 1주 빠르게, 다른 한 과목은 시험이 1주 느리게 치뤄지는 터라 한 숨을 돌렸지만...

ICPC 온라인 예선이 있던 10월 21일에 시험이 하나 정해져 있었다! 심지어 오후 1시부터 3시까지라 일부 겹치기까지 했고. 해당 과목 교수님의 연구실을 약속도 잡지 않고 무작정 찾아가서 혹시 일정 조정이 가능한지 여쭙는 심각한 무례를 저질렀다. 나중에 들으니 이런 개인적(이지만 중대한) 사정으로 시험을 일부 앞당기거나 늦추는 학생이 나 말고 둘이나 더 있더라. 하나는 5급 공무원 시험이었고, 다른 하나는 취업 면접이었다. 그 둘에게도 뒤늦지만 행운이 깃들길.

여하튼 발악을 통해서 ICPC 참가 확인서를 받고 성공적으로 시험 시작 시간을 한 시간 앞당겼다. 제대로 대회장에 도착하려면 남들 두 시간 보는 시험을 한 시간 반 만에 끝내야 하지만, 다행히 그렇게 어렵지 않은 시험이라 그것에는 문제가 없었다.

성공적으로 일정 조정을 마치면서 시험 공부도 하고, ICPC 참석을 위한 각종 정보 입력과 스크린샷 제출... 이것저것 해결하느라 다들 고생이 많았다.

 

그리고 각종 기각 사유를 전부 회피하며 참가 팀으로 등록을 마칠 수 있었다. 예비소집의 날이 다가오고 있었다...

3인 전부 참가할 필요는 없었으나 대회 직전 환경을 테스트하기 위해서는 무조건 참가하는 것이 유리했다. 다른 둘도 그렇게 생각했는지 모이기로 했고, 예비소집에서 대회 전 마지막으로 손을 맞춰 보기로 했다.

예비소집 문제로는 2022 인터넷 예선의 A(25943), E(25947), H(25950)이 순서대로 나왔다.

A는 맞왜틀을 많이 해서 기억에는 남아 있었는데, 대체 왜 맞왜틀을 당했는지는 기억이 안 나는 문제. 누가 잡아도 무난하게 구현이 가능할 문제였고, 컴퓨터 앞에 앉아 있던 now_cow가 구현하여 무난하게 AC를 얻어 냈다.

E는 A의 구현이 진행되는 동안 내가 해석해서 qttw456과 어떻게 풀지를 생각하고 있었는데, 그리디로 하는 것은 확정인 상황에서 그 그리디를 어떻게 적용시키느냐를 좀처럼 떠올리지 못하고 있었다. 그러다 슬라이딩 윈도우 식으로 누적합을 짜 보면 어떨까(회장에서는 dp라고 이야기했던 것 같은데, 사실 누적합이 맞았다) 하는 발상을 내가 했고, 구현도 내가 해 보겠다고 컴퓨터를 넘겨받아서 AC를 받아 왔다.

H는 일단 난이도부터가 정상이 아닌 문제라는 게 딱 보였다. 실제로 논문 베이스인데다가 푼 사람이 딱 한 명밖에 없다!! 처음에는 앞의 두 문제 풀고 시간도 남으니 풀어볼까 하고 잡았는데, 잠깐만 봐도 해 볼 만한 문제가 아니라는 것을 바로 느낄 수 있었다. 처음에는 직사각형 N개가 있으면 N개로 쪼개서 같은 문제 N번 풀기라는 의견을 냈는데, 직사각형을 무시하고 가는 게 더 이득인 케이스가 있었어서 그냥 택도 없는 의견이었다. 그냥 남은 시간 동안 팀노트나 대충 만져보기로 했다.

C++ 뤼카가 너무 길어서 그거 버리고, 파이썬 코드를 넣기로 했다. 네 줄짜리 코드라서 오히려 그게 이득이었다. 그리고 HLD니 뭐니 하는 저세상 알고리즘을 버리고 파이썬으로 된 다익스트라, 크루스칼을 이용한 MST, 밀러-라빈과 폴라드 로, 그리고 FFT를 집어넣기로 했다. 그 넷 중 어느 하나라도 나오면 구현할 수 있는 사람이 하나에서 셋으로 늘어나니까.

 

4. 3 HOURS FIGHTERS

마침내 대망의 본선 날. 연세대학교 공D915에서 대회가 치뤄졌다. 그 전 있었던 전공과목 중간고사에서 모든 문제를 제대로 풀어내고 가벼운 발걸음으로 회장에 도착해서 세팅하기 시작했다. 자리가 원탁형이 아니라 일자형으로 되어 있었고, 예비소집 때 아예 한 쪽으로 컴퓨터를 몰아놓고 나머지 두 사람이 이야기를 할 공간을 만드는 게 더 나았다.

세팅이 끝날 때쯤 나머지 두 팀원이 도착했고, 자리에 앉아서 문제가 공개되기만을 기다렸다. 미리 문제지를 프린트해놓을 수 없어서 일단 거저 주는 한 문제를 다른 문제들의 프린트가 마쳐지기 전에 끝낼 수 있으면 그러기로 했다.

그리고 오후 2시 정각이 되고...

0:03 C AC (First Solve)

나는 이 문제 채점이 끝나고도 한참동안 내가 First Solve를 따내리라고는 생각도 못 했다. 간단한 문자열 순회 문제였는데, C++은 문자열 처리가 조금 성가신 면이 있어서 파이썬 주력인 내가 컴퓨터를 잡았다. HAPPY 속에 있는 영문자와 SAD 속에 있는 영문자 비율을 세는 문제였는데, 파이썬은 letter in 'HAPPY'와 같은 식으로 간단하게 구현을 마칠 수 있어서 내가 잡는 것이 결론적으로 맞았다.

예제 두 개 맞는 거 확인하자마자 별 고민도 안 하고 냈고... 그리고 스코어보드 맨 위에 걸려버렸다. 얼라리...? PS 인생 최고 성과가 이런 데서 튀어나오나??

0:30 D AC (+3)

첫 단추가 잘 꿰어져서 나머지 문제들을 차분하게 볼 시간이 났다. D는 무슨 문젠지 하나도 기억이 안 난다 ㅋㅋ... 한국어 문제였다는 것, now_cow가 짜다가 내가 이어받아서 구현해서 정답을 따냈다는 것, 그리고 개 멍청한 짓을 해서 출력도 안 하는 코드를 내버리는 개 ㅄ짓을 했다는 것 이 세 개 정도만 기억한다.

해서는 절대 안 되는 짓이었는데 퍼솔을 먹은 전적 덕에 용서받았다고 생각한다.

0:41 K AC (+1)

내친 김에 해석을 마친 K번 문제까지 내가 구현했다. 모든 별 쌍의 중점 중 최빈값의 등장 횟수를 구하라는 건데, 쉬워 보이기도 하고 생각보다 시간 제한 널널할 것 같다는 생각을 해서 \(N^2\)을 냈다가 시간제한에 걸렸다. \(N^2/2\)는 통과되는 거 보고 뒷목 잡을 뻔했다. 구현이 상대적으로 간편해서 절반 커팅을 안 했는데 상수커팅 하나에 정답 오답 여부가 갈리다니... 기분이 별로 안 좋았다.

2:08 G AC

수학 문제였던 E번을 구현하겠답시고 K에서 AC를 따낸 후 약 40분 가량 나 혼자서 컴퓨터를 잡고 있었다. 나머지 둘 보고 해답 떠오르면 바로 알려달라는 말을 남기기는 했지만... 하면 안 되는 짓이었다. 케이스가 정말 개 복잡하게 나뉘어서 쉽게는 못 풀 문제였다. 하나의 케이스를 생각하지 못하고 간과하여 도전한 게 이번 대회에서 내가 한 가장 큰 실수였다.

마지막 한국어 문제인 G번과 답이 나올락 말락 한 I번을 동시에 굴리기 시작했다. qttw456이 해석을 마쳐서 나에게 I를 들려주고, 나는 G를 푸는 방법을 now_cow에게 전달하고...

n-th element를 찾는 것이긴 한데, 750만 개의 수를 모조리 정렬하면 시간제한인 0.5초에 그대로 걸려버린다. 악랄함?에 치를 떨며 이런저런 아이디어를 내 봤는데, 0과 1 사이 기약분수는 0.5를 기준으로 대칭일 테니 기약분수의 수만 입력받아 절반을 넘으면 0.5보다 큰 절반만 정렬하고, 절반을 넘지 못하면 0.5보다 작은 절반만 정렬하는 것이 원안.

4조각을 내니 8조각을 내니 10조각을 내니 계속 이야기해 보다가 도달한 결론은 10조각 정렬이었다. 시간이 애매해서 C++ 유저 now_cow에게 구현을 맡기고, 로컬에서 이것저것 씨름하다가 단박에 해결. 한 번만에 통과한 것이 행운일지도 모른다는 생각을 했다.

바로 뒤에 모르고리즘 회장님이 팀장으로 있는 3렌지 팀 SCC가 있었는데, G번 지랄맞다는 소리가 아주 생생하게 들려왔다. 짜증나는 문제임은 확실하다. kiwiyou 말로는 페리 수열로 바로 풀린다는데, 검색이 불허되는 ICPC에서 그런 생각이 바로 튀어나올 리가 만무하다... 이거 웰노운 아니야!!

3:00 I WA (+5)

그리고 남은 한 시간여 동안 답의 윤곽이 어느 정도 잡히는 I번만 공략했다. 다른 문제에 투자할 시간은 없었고, 그냥 5솔로 속 편하게 본선 가고 싶었다는 마음이 컸다. 우리 팀 실력으로 제로베이스에서 한 시간만에 구현까지 완벽하게 끝낼 만한 문제는 적지 않았지만, 혹시나 말리면 그만큼 아쉬운 것은 없으니...

내가 이걸 동물 관람 시간이 끝나는 시간이 빠른 순으로 정렬 후 dp로 풀겠다는 아이디어를 냈고, 컴퓨터를 잡고 있었던 now_cow에게 설명했다. 이 과정에서 살짝 전달이 어긋나서 구현에서 오류가 생겼다. 2틀 적립 후에 머릿속에서 풀이가 완전히 완성된 내가 잡으면 할 수 있을 것 같다는 근자감이 튀어나와서 파이썬으로 처음부터 구현을 시작했는데, 끝나기 9초 전에 제출한 코드마저 WA를 받으면서 솔브 수 하나를 따내는 것에는 아쉽게 실패했다.

끝나자마자 :god:-회장 Serendipity__에게 풀이를 물어봤는데, 걸러야 할 요소 하나를 실수로 덜 걸렀다고 한다. 아이고...

 

5. 총평

분명 합 안 맞춰 본 팀이 이렇게 오는 게 쉽지 않은 일이기는 한데, 욕심이 많아서 그런지 아직은 만족이 덜 된다. 졸업 때문에 PS와 멀어지는 qttw456를, 그리고 이게 처음이자 마지막 ICPC인 나를 위해서 이번에 본선에 가겠다는 일념으로 대회를 치뤘는데, 대회를 복기해 보니 내가 친 사고만 한 무더기다.

본선 진출이 확정된다면 킨텍스 가기 전에 두 사람 졸라서 리저널 기출들 풀면서 대비 한 번 해 봐야겠다. 시험이 끝나면 밀린 코포랑 앳코더도 좀 치고... 그린 복귀를 넘어 민트 정도는 가야 PS에서 은퇴하더라도 기분 좋게 은퇴하지 않겠는가.

대회 내내 택도 않는 실수와 사고만 치면서 계속 짐덩어리만 달아 준 것 같아서 두 팀원에게 너무 미안하고, ICPC에서 4솔 51등이라는 성적을 거두는 데 크게 일조한 두 사람의 발끝이라도 쫓아가고 싶다. 진짜로, 아직 나는 부족한 게 맞다.

 

본선이래!!!!!!!!!!!!!!!!!!!!!!

+) 진출했다!!!!!!!!!!!!!

다음 달에 본선 후기로 돌아오겠습니다.