저희 SushidoQueue팀은 최종성적 16등으로 ICPC를 마치게 되었습니다. 당초 목표였던 한양대 1위/전체 14위(수상권) 중 하나밖에 이루지 못한 반쪽짜리 성공이긴 하지만, 그 반쪽도 거의 기적적으로 이루어진 것이기 때문에, 결과에는 어느 정도 만족하긴 합니다. 애초에 두 목표 다 ‘설마 되겠어?’ 싶었던 목표였는데 하나로도 이룬게 어디야 싶기도 하고요.
대회 전 연습
저희팀은 ICPC 인터넷 예선 전(및 UCPC 본선 이후)에 4번, 예선 후 2번 총 6번의 팀연습을 진행했고, 지난주(11/6일)에 진행한 CERC 2020 팀연습을 제외한 모든 팀연습의 내용을 블로그에 포스팅해놓았습니다.
팀연습을 진행하면서 여러가지 문제점을 발견할 수 있었는데, 그중 무엇보다 치명적인 것은 제 실력이 ICPC 인터넷 예선을 기점으로 나날이 저점을 찍고 있다는 것이었습니다. 예선때는 제 실책으로 B번과 C번을 못 풀었고, ICPC 요코하마 리저널 팀연습때는 구현이 복잡하지도 않은 B번을 구현을 못해서 구현 ‘해줘’병이 도지더니, CERC 2020 팀연습때는 팀이 4솔브를 할 동안 저는 아예 한 문제도 풀지 못했습니다. 이렇게 팀연습을 내리 죽을 쑤다보니 자신감도 떨어져갔고, 이대로는 안되겠다 싶어 마지막 팀연습 이후 개인연습을 따로 진행했습니다.
11/7 - CERC 2014
최종 4솔브, 당시 스코어보드 기준 31등의 성적으로 마무리했습니다. F번을 못 풀고 끝낸게 아쉬웠는데, 해당 문제 태그가 dp인걸 보니 제가 dp를 어지간히 못푸는구나..싶었습니다.
11/7 - NEERC 2015
최종 5솔브, 당시 스코어보드 기준 59등의 성적으로 마무리했습니다. 이날 개인 연습 두세트를 연달아 뛰면서, “어라, 나 혼자 뛰어도 성적이 팀연습때랑 비슷하게 나오네?” 하는 생각이 들면서, 여태까지 뭘 한거지 싶었습니다. 제가 평소 팀연습때(특히 예선 이후에) 푼 문제 수를 보면 절대 저희 팀이 artichoke42 원맨팀이기 때문인 건 아닐거고, 개인연습때와 팀연습때 제 태도 차이일거라 생각해서 제 지난 팀연습들을 되돌아봤습니다. 그리고 제가 찾은 문제점은 크게 두 가지였습니다.
- 실시간 스코어보드를 지나치게 의식한다.
- 한 문제에 집중하지 못하고 동시에 여러 문제를 본다.
특히 1번때문에 집중이 깨지는 경우가 많았던 것 같습니다. 문제 풀다가 막히면 바로 스코어보드부터 찾곤 했으니.. 따라서 리저널때는 스코어보드는 웬만하면 한 문제 풀고나서 다음으로 풀 문제 참고용정도로만 쓰는 걸 목표로 해야겠다고 다짐했습니다.
11/8 - ICPCLatin 2018
최종 9솔브, 당시 스코어보드 기준 7등을 달성했습니다. 이날은 컨디션이 고점을 찍었던 것 같네요. 구현 실수도 디버깅 코드 수정 안하고 제출한 E번을 제외하면 없었어서 페널티 관리도 잘 된거같구요. 다만 F번 짜다가 소스를 날려버려서 그대로 자체종료해버린건 지금 생각해보면 아쉽네요. 시간 한시간정도 남아있었는데..
11/10 - SEERC 2018
최종 4솔브, 당시 스코어보드 기준 16등의 성적으로 마무리했습니다. 풀이를 거의 찾았다고 착각한 K번가지고 뇌절하느라 정작 쉬운 문제인 J번을 읽지도 못한게 아쉬운 셋이었습니다. 뭐 그래도 이셋은 초반에 엄청 말려서 중도탈주할까 고민도 했던 셋이었는데 이정도면 선방했다고 생각합니다.
11/11 - ICPCJP 2017
최종 5솔브, 당시 스코어보드 기준 14등의 성적으로 마무리했습니다. G번 구현실수를 좀 많이해서 페널티 쌓인거랑, F번의 마지막 아이디어인 ‘단절선’을 못 떠올려서 못 푼게 아쉬웠습니다.
11/12 - NWERC 2018
최종 5솔브, 당시 스코어보드 기준 45등의 성적으로 마무리했습니다. 사람들이 많이 푼 E, G, J번이 모두 구현문제라 그대로 폭사했네요.. 여전히 구현에 많이 약하다는 걸 깨달을 수 있었던 셋이었습니다.
막판에 진행한 셋을 살짝 망친감이 있긴 하지만, 한 주 동안 진행한 개인 연습 덕에 ‘solved.ac 기준 웬만한 플래티넘 문제는 풀 수 있다’는 자신감을 다시 얻기엔 충분했던 것 같습니다. 그 외에 스코어보드는 언제, 어느정도 주기로 봐야하는지, 문제 풀다 말렸을때 대처법 등등, 대회 전략에 대한 감도 덤으로 얻을 수 있었습니다. 이제 남은건 다음날 대회를 잘 치는 것만이 남았습니다.
대회 당일
저희팀은 대회 시작시간인 12시보다 2시간 이른, 10시에 모여 아침을 든든하게 먹었습니다. 사실 ICPC 예선때부터 3주 내리 지각한 kyaryunha가 오늘도 지각할까 살짝 걱정됐었는데, 이번엔 다행히 정시에 왔습니다. 이후 11시까지 프린터, 노트북, 카메라 등 잡다한 세팅과 팀노트 출력을 마쳤고, 나머지 한 시간동안 저희팀의 유구한 전통인 ‘A번 폭탄돌리기’를 비롯한 잡담을 했습니다. 폭탄돌리기 결과 제가 A번부터 읽게 되었습니다. ‘jame0313님은 템플릿코드를 짜야하고, kyaryunha는 문제를 배분해야하니 A번을 볼수 있는건 너밖에 없다’는 논리를 반박할 수가 없었기 때문에 어쩔수 없었네요..
그런데 사실 다 의미없는 논쟁이었습니다. A번은 딱 봐도 초반에 풀 문제는 아닌 것 같았던 HLD문제가 있었거든요. 예선때 Mo’s가 나왔어서 본선때는 트리버전 쿼리유형인 HLD가 나오지 않을까? 하는 막연한 생각을 하긴 했는데 진짜 나올줄이야..
B. Double Rainbow (Solved by artichoke42, 24min, 제출 3회)
A번을 거른 뒤 본 B번문제는 k개의 색깔의 노드를 적어도 하나씩 포함하는 연속된 구간 P’의 최소 길이를 구하되, P’의 여집합도 k개의 색깔의 노드를 적어도 하나씩 포함해야 하는 문제였습니다. 간단한 투 포인터 문제라고 생각하고 바로 컴퓨터를 잡았고, 금방 구현해서 예제가 잘 나오는 것을 발견하고 제출했지만 WA. 알고보니 문제를 최대 길이를 구하는 것으로 잘못 해석했더군요. 이 부분을 고쳐서 제출했지만 또 WA. 앞부분만 최소 길이를 구하는 코드로 바꿔놓고, 뒷부분은 안 고쳤더군요.. 뒷 부분까지 고치고 나니 그제서야 AC가 떴습니다. 시작부터 순탄치 않았네요 ㅎㅎ..
C. Find the House (Solved by jame0313, 28min, 제출 1회)
제가 B번을 구현할 동안 jame0313님도 C번 구현을 거의 마쳤습니다. 예제가 잘 나오는 것을 확인하고, 제출해서 한번에 AC를 받았네요. 당시엔 문제를 아예 읽지도 못했고, 나중에 업솔빙할 때 돼서야 봤는데, indegree가 1이고 outdegree가 0인 정점을 찾는 단순 구현문제였다고 합니다.
D. Friendship Graphs (Solved by artichoke42 & jame0313, 158min, 제출 6회)
우리팀이 말린 가장 큰 원인
D번은 주어진 그래프를 2개의 완전그래프로 분할하되, 가능한 방법이 여러개라면 두 그래프의 크기 차이를 최소화하는 문제였습니다. 처음엔 주어진 그래프 \( G \)를 반전시킨 그래프 \( \bar{G} \)가 이분그래프인지 여부를 판단하는 문제라고 생각하고 제출했지만 WA를 받았습니다. 원인은 \( \bar{G} \) 의 컴포넌트가 하나가 아닐 수 있기 때문이었습니다. 원인까지는 찾았는데, 이걸 어떻게 해결하지? 싶어서 jame0313님에게 헬프를 요청했습니다.
jame0313님은 dp로 풀수 있을 것 같다고, \( \bar{G} \)를 컴포넌트 단위로 분리하는 코드만 작성하면, 나머지는 본인이 하겠다고 했습니다. 그래서 저는 컴포넌트 단위로 분리하는 코드를 작성하고, jame0313님에게 넘겼습니다. dp 코드를 완성한 jame0313님은 예제가 잘 나오는 것을 확인하고 제출했으나.. 이번엔 No Output이 떴습니다. jame0313님이 dp코드를 계속 고쳐가면서 No Output 두번 더 띄우고 나서야 원인을 찾았지만, 이번엔 WA가 떴습니다. 이쯤에서 스코어보드를 봤을 때 상위권 팀들은 이미 5~7솔을 했다는 것을 확인하자, 서서히 멘탈이 깨지기 시작했습니다.
WA가 뜬 원인은 한참 뒤에서야 찾았는데, \( \bar{G} \)를 이분그래프로 나눌 수 없으면 {-1, -1}을 반환하도록 하는 코드에 문제가 있었습니다. 제 코드는 문제 없을 줄 알았는데 제 잘못이었네요 ㅋㅋㅋㅋ.. 아무튼 이 부분을 고치니 AC를 받았습니다.
참고로 이 이후로 프리즈될 때까지 추가로 푼 문제가 없었습니다. 70분대까지 1솔 상태였던 인터넷 예선때보다 더 피말렸네요..
F. John’s Gift (Solved by jame0313, 215min, 제출 6회)
F번은 배열 A와 배열 B가 주어지고, 배열 A의 각 원소와 배열 B의 각 원소를 ‘하나를 제외하고’ 매칭시킬 때, 매칭된 두 원소의 차이의 최댓값을 최소화하는 문제였습니다. 정확히는 배열 A의 어떤 원소를 빼야 최댓값이 최소화되는지를 출력해야 했고, 이러한 경우가 여러개라면 가장 작은 원소를 빼야 했습니다.
jame0313님이 한참전부터 이분탐색+그리디라고 주장했고, 저도 그게 맞는 풀이라고 생각해서 제출했지만 WA가 여러번 떴었습니다. kyaryunha와 jame0313님이 테스트 케이스를 계속 만들어본 결과 동점자 처리하는 쪽에 문제가 있다는 것을 확인하고 고쳐서 AC를 받았습니다.
G. Logistical Warehouse 2 (Solved by artichoke42, 237min, 제출 1회)
G번은 모든 노드가 warehouse 노드로부터 거리 K 이하가 되도록 하려면, warehouse를 최소 몇 개를 배치해야 하는지 묻는 문제였습니다. 당시에는 작년 UCPC에 출제된 전단지 돌리기랑 비슷하다고 생각했는데, 지금 보니 거의 무관한 문제였네요.
풀이는 팀원이 이 문제 읽자마자 예상했던 것처럼 트리dp였습니다. 현재 노드의 자식노드 중 warehouse 노드와의 거리의 최솟값과 최댓값을 관리하면서 푸는 문제였습니다. 풀이를 도출하기 전까지 온갖 삽질을 다 했었는데, 로컬에서만 삽질한 덕에 제가 푼 문제중 유일하게 한번에 AC를 받은 문제가 되었습니다. 이거마저도 WA가 떴으면 멘탈 제대로 무너졌을 것 같네요. ㅋㅋㅋ
L. Trio (Solved by jame0313, 270min, 제출 2회)
보드게임 Set을 기반으로 출제된 문제. n개의 4자리 수 중 3개를 뽑았을 때, 각 자리 수가 서로 다르거나, 모두 같은 경우의 수를 찾는 문제였습니다. 이 문제도 jame0313님이 한참 전부터 수들을 어떻게 잘 나누면 될 거 같다고 했었는데, 저는 풀이를 이해하지 못해서 직접 짜보라고 했고, F번이 풀린 뒤부터 본격적으로 구현에 들어갔습니다.
저는 이때 E번을 열심히 잡고 있었기 때문에 L번 풀이가 어떤지, 진행 상황이 어땠는지는 기억이 잘 나지 않습니다. 아무튼 WA가 한번 뜬 뒤 AC를 띄우셨습니다.
E. Grid Triangle (Solved by artichoke42, 283min, 제출 5회)
다른 것보다도 해석이 제일 어려운 문제였습니다. 일단 영어 3등급따리답게 ‘cuboid’가 뭔지를 몰라서 시간이 좀 끌리기도 했습니다. 나중에 직육면체라는 걸 추측해내긴 했지만… 그런데 이걸 이해하고 나서도 왜 예제 1번 답이 48이였는지 이해할 수 없었습니다. 브루트포스 돌렸을 때 제 답은 288이 나왔거든요.
지문을 한참 읽고서야 숨은 조건들을 몇 개 더 찾을 수 있었습니다. 첫째로 어느 한 좌표값이 0이어서는 안되고, 둘째로는 서로 다른 축의 좌표의 절댓값이 서로 같은 경우 또한 제외해 주어야 했습니다. 여기에 중복되는 경우를 제거하고 나니 드디어 브루트포스 결과와 예제의 답이 일치하기 시작했습니다.
그리고 A, B, C값을 바꿔가며 브루트포스를 반복적으로 돌린 결과, 규칙을 찾을 수 있었습니다. 일반성을 잃지 않고 A \( \le \) B \( \le \) C라고 했을 때, \(a, b, c\) 모두 A보다 작거나 같은 범위 내에서 \(a + b = c\)이고, \(a \ne b\)인 쌍의 개수에 48을 곱한 것과, \(a, b\)는 A보다 작거나 같고, \( c \)는 A보다 크고, B보다 작거나 같은 범위 내에서 동일한 조건을 만족하는 쌍의 개수에 16을 곱하면 답이 된다는 것을 알게 되었습니다.
다만 이거 짤 때도 실수를 좀 많이 해서 또 페널티를 쌓았네요. WA를 4번 받고 나서야 AC를 받을 수 있었습니다.
5시간 내내 피말렸던 셋인 만큼, 마지막 E번 AC는 짜릿했습니다. D번 풀때까지만 해도 이거 또 예선꼴 나는건가, 일주일간 했던 연습도 아무 소용 없었나 싶었지만, 저와 jame0313님이 각자 한 문제씩 잡고 우직하게 풀어냈고, kyaryunha는 나머지 팀원들이 코딩하다 막혔을때 디버깅 과정에서 결정적인 단서를 제공한 덕에 저희 팀 성적을 7솔까지 끌어올릴 수 있었던 것 같습니다.
남은 시간동안은 5시간동안 (웬일로) 제대로 보지도 못했던 스코어보드를 확인하고, 페널티를 계산하면서 범인찾기도 하고, 잡담도 했습니다. 사실 페널티를 쌓은 범인은 안봐도 접니다 스코어보드를 봤을 때, 교내의 다른 팀이 프리즈된 문제를 모두 맞았다 쳐도 교내 1등이라는 것을 확인하고 안도할 수 있었던 한편, 반대로 프리즈 이후 한 문제도 못 풀었다면 교내 1등은 커녕 교내 꼴찌가 될 수도 있었다는 사실을 알게 되었습니다. 이번에 저희 팀이 얼마나 말렸는지를 새삼 실감할 수 있었네요. 그리고 나중에 스코어보드 깔때 뭐라도 더 있어보이는 것처럼 만들기 위해, K번에 하나를 제출하고 대회를 끝마쳤습니다.
(자료제공: kyaryunha)
대회가 끝난 후에는, 팀이름값(SushidoQueue)를 하기 위해 뒷풀이로 왕십리 스시도쿠로 갔습니다. 입장 대기시간 끝날때쯤 딱 ICPC 풀이방송을 시작해서, 저녁 먹을동안 스코어보드 까는 걸 봤습니다. 사실 대회 막 끝났을 때는 수상권도 기대해볼 만 하다고 생각했었는데, 막상 스코어보드 까보니 E, F, G, L 모두 생각보다 푼 팀이 많았고, 저희팀 페널티가 너무 커서 무리였나 봅니다. 조금 아쉽네요..
총평
전에 UCPC 후기 글에서 언급했듯, 올해 팀을 구성했을 때 제 개인적인 목표는 ‘팀에서 1인분 하기’였습니다. 지금 와서 돌아보면 ICPC 예선때는 약간 애매하지만 대체적으로 성공적이었음은 물론, 이제 팀내 1인분이라는 소박한 목표를 떠나 ICPC 수상이라는 큰 목표를 바라보는 저를 보며 올 한해 동안 크게 성장했음을 느낄 수 있었습니다. 하지만 올해의 성장해도 불구하고 ICPC 수상의 벽은 높았는데, 다음에 참여할 땐 지금보다 더더욱 성장해서 이 벽을 넘어보도록 하겠습니다 :)