2022 ICPC Seoul Regional 후기

작성일 | In |

팀 구성

팀 구성은 작년 12월 중에 진행되었고, 나(ansol4328), deuslovelt, hojoon0205 로 이루어져있다. 19년도에 hojoon0205와 UCPC에 나가서 꽤나 좋은 성적을 거둔 기억이 있어, 복학 후 22년도에 함께 팀 대회 참가를 계획하고 있었다. ICPC가 3인 대회인 만큼 남은 한 자리에 누구를 영입해야할지 군대에서 고민이 있었고, 마침 내가 없는 20, 21년도에 성대에서 ICPC 본선 및 SCPC 수상자가 나오면서 이들 중 한 명과 함께하면 좋을 것 같다는 생각이 있었다. 20년도 팀 사람들의 경우 대부분 22년도에 졸업이나 군 입대를 앞두고 있는 것을 알고 있었기 때문에, 작년 수상팀 팀원 중 팀원을 못 구한 분을 영입할 계획을 세웠었다. 그러던 중 먼저 deuslovelt로 부터 영입 제안이 왔고, 당시 양쪽 모두 한 자리만 채우면 되는 상황인지라 나와 hojoon0205도 역으로 영입 제안을 하게되었다. 기존에 약속된 팀원을 두고 다른 팀에 가는 것이 쉽지 않기 때문에 무산될 것으로 생각했지만, deuslovelt가 우리 팀으로 오는 것으로 결정을 하였고 그렇게 12월에 팀이 결성되었다.

우리 팀에서 각자의 강점은 다음과 같다고 생각한다.
ansol4328 : 자료구조, 웰노운 (2명이 함께 풀이를 설계하는 경우, 특정 상황이나 조건에서 필요한 자료구조나 웰노운 테크닉을 주로 제시한다.)
deuslovelt : DP (팀연습 중 깡 DP 다이아 문제를 자주 풀어낼 정도로 우리 팀에서는 독보적으로 DP에 강점이 있다.)
hojoon0205 : 수학, Constructive (3명 중 코드포스 레이팅이 가장 높고, 우리 팀의 수학 전담이며 문제 풀이에 필요한 가설을 잘 세운다.)

팀연습

12월에 팀이 구성되고 hojoon0205가 3월에 전역을 함으로써 1학기 개강과 함께 오프라인 팀연습을 진행하였다. 그 이전에도 PTZ 2022 winter camp도 함께 참여하였고 온라인으로 2~3차례 연습을 진행했다. 학기 개강 이후에는 오프라인으로 주 1회 해외 리저널을 코드포스 gym에서 버츄얼 참가를 하는 식으로 진행하였다. (세어보니 총 25번을 진행하였다.) 혼자서는 풀기 어려운 문제일지라도 2명이 같이 논의하면 풀 수 있다는 작년 수상자인 deuslovelt의 경험을 기반으로 팀 전략을 수립하게 되었다. 실제로 연습 중 초반부에 가장 중점을 둔 것이 서로의 풀이를 검증해주고, 자신의 생각을 팀원과 오류없이 공유할 수 있도록 소통 능력을 키우는 데 집중하였다. 사실 18, 19년도는 팀연습을 이렇게까지 체계적으로 생각하고 접근해본 적이 없어 얼마나 큰 영향이 있을까 싶었지만, 서로 소통이 원활해질수록 팀연습 결과도 점점 더 좋아지는 것을 볼 수 있었다.

주로 연습때와 대회 중 흐름을 생각해보면 초반부 쉬운 문제를 각자 풀어낸 이후, 플래 이상 문제의 경우 2명이 같이 논의하여 풀이를 내는 형태로 진행되었다. 추가로 만약 어려운 DP 문제를 발견한 경우 deuslovelt가 긴 시간동안 집중하여 풀이를 내었고, 그동안 나와 hojoon0205가 나머지 문제를 함께 풀어내는 식으로 진행되었다. 2명이 함께 풀이를 구상하는 경우 초반 아이디어 도출이 뛰어난 hojoon0205가 주로 가설을 세우고 검증한 뒤, 이를 기반으로 먼저 naive한 풀이를 설계하고 이를 최적화시킬 수 있는 자료구조나 테크닉을 다른 팀원이 제시해주는 상황이 많았다.

팀명 비하인드

위에서 언급했듯이 우리 팀은 각자가 강한 분야가 크게 겹치지 않는다고 생각한다. 비록 3명의 코포 레이팅은 max 기준 2200점 중반과 2090점대로 찐렌지 1명, 퍼플 상위 2명에 불과하지만 각자의 부족한 점을 보완해줌으로써 팀연습때 결과만큼은 레드가 포함된 타 대학 팀들과도 비등한 성적이 나왔다. 꽤나 팀연습 성적이 좋았기 때문에 충분히 ICPC 본선에서 경쟁력이 있다고 생각하였고, 3명 다 PS 판에서 잘 알려지지 않은 언더독인 만큼 이와 관련되어 팀명을 짓자는 의견이 나왔다. 이렇게 Underdog 이 Underduck 으로 바뀌었고, 마지막에 한번 더 비틀어 Undergoose 라는 팀명으로 최종 결정이 되었다.

ICPC 예선
예선 스코어보드

최근 성대 내부 팀의 평균 실력이 상향 평준화된 만큼, 성대 내부 1위를 목표로 예선에 참가하였다. 초반에 한글 문제를 위주로 잡았고, 운좋게도 가장 쉬운축에 속한 문제들을 바로 잡아서 초반 러쉬에 성공하였다. (가장 쉬운 3문제를 풀었을 때 전체 3등까지도 올라갔다.) 그 이후에도 대부분 빠르게 풀이가 나와서 순조롭게 진행되나 싶었으나, F번 문제를 내가 SCC로 구현한 결과 TLE라는 결과를 받게 되면서 페이스가 말리게 되었다. 구현력이 많이 떨어진 상태인지라 SCC를 올바르게 짰음에도 확신이 없었고, 다른 팀원에게 넘겨주고 코사라주 방식으로 구현을 하고, 인접 리스트가 아닌 단순 배열로 최적화하는 식으로 AC를 받았다. (나중에 알고보니 교내에서 다른 팀도 똑같은 경험을 한 팀이 있었다.) 그렇게 F번 문제에 말리고 있는 동안 deuslovelt가 J번을 풀 수 있을 것 같다는 말을 하였고, 실제 러닝타임은 구현을 해봐야 알 것 같다고 하였다. 첫 풀이를 제출한 이후 TLE가 나왔고, 얼마 지나지 않아 루트언저리 숫자가 예쁘겠죠? 라는 말과 함께 약간의 수정 이후 AC를 받아냈다. 프리즈 전에 7솔브를 만들면서 본선 진출은 확실하다고 생각하였고, 남은 시간은 3명이 B번을 고민하다가 끝이 났다.

ICPC 본선
본선 스코어보드

올해는 3년만의 오프라인 본선 대회가 일산 킨텍스에서 열렸다. 오랜만에 참여하는 ICPC 본선인 만큼 설렘도 있었고, 1년 동안의 노력을 보여줄 순간이 왔다는 부담감도 있었다. 예비소집때는 환경 점검을 진행하였는데, 평소에 vscode에서 연습을 했었기에 vscode를 사용하려고 했지만 아무런 extension이 없는 깡통 vscode라 자동완성이 아예 없다는 치명적인 단점이 있었다. 그래서 코드블럭을 사용해보자는 팀원의 제안에 코드블럭도 써봤지만 인덴트가 박살나는 것을 보고 뜻밖의 문제를 만나게 되었다. 그러던 중 CLion이라도 써보자는 생각에 사용을 해보았고 가장 평소 연습하던 환경과 유사한 느낌이라 본선대회 때도 CLion을 쓰는걸로 즉석에서 결정됐다. 이후 숙소로 이동하여 하루를 보낸 뒤 대회에 참가하였다.

대망의 본선 대회날 아침을 간단히 떼우고 1층에서 팀원을 기다리던 중, 같은 숙소에서 ICPC 출제 교수님들이 나오는 것을 보았다. 킨텍스에서 가장 가까운 곳으로 잡긴 했지만 교수님들까지 여기에 있을거라곤 생각을 못했는데 상당히 신기한 장면이었다. 그렇게 1층 로비에서 팀원들이 모두 모인 이후 대회장으로 이동하였고 대기실에 대기하다가 9시 반정도에 대회장에 입장하였다. 10시에 대회가 시작되었고 컴퓨터 앞에 앉은 내가 초기 환경세팅을 담당하였다.

0 ~ 30min

  • 내가 환경 세팅을 하는 동안 deuslovelt가 평소 연습처럼 문제를 훑어보고 나머지 팀원에게 문제 분배해 주었다.
  • 얼마 지나지 않아 J번 문제가 해결되었고, deuslovelt는 I를, 나는 D를, hojoon0205는 C를 처음에 읽었다.
  • I번 코딩이 가능하다고 deuslovelt가 말했고 제출 결과 WA를 한번 받게 되었다. (I WA ?min)
  • 그 사이에 J를 hojoon0205가 읽고 바로 풀 수 있다고 하여 컴퓨터를 넘겨받고 AC를 받았다. (J AC 23min)
  • 나는 D가 제곱 풀이 이외에 잘 떠오르지 않아 F를 읽고 풀이가 떠올랐고, E를 읽었다.

30 ~ 60min

  • deuslovelt가 버그를 잘 고쳤고 I를 풀었다. (I AC +1 34min)
  • 내가 F번 문제 구현을 하기 전에 먼저 E번 문제를 deuslovelt에게 설명해주었다. 이후 F를 짜서 제출했고 맞았다. (F AC 47min)
  • F를 맞춘 이후 deuslovelt가 E 풀이를 냈고 구현을 했으나 WA를 1번 받았다. (E WA ?min)

60 ~ 90min

  • 얼마 지나지 않아 E번을 deuslovelt가 고치고 풀었다. (E AC +1 75min)
  • D번 문제에 대하여 내가 제시한 제곱 풀이 DP에 참조되는 인덱스가 단조성이 있을 것 같다는 추측으로 투 포인터를 넣은 코드를 hojoon0205가 짰고 WA가 나왔다. (D WA ?min)
  • L번 문제에 대하여 hojoon0205가 항상 길이 3짜리 사이클이 존재할 것으로 추정된다. 라는 가설을 세웠고 별로 맞춘 팀이 없었지만 가설에 기반하여 코딩을 하였고 WA가 나왔다. (L WA ?min)

90 ~ 120min

  • 당시 가장 많이 풀리던 문제가 K였고 나와 deuslovelt가 동시에 읽기 시작하였다.
  • 문제 이해를 더 먼저한 deuslovelt가 설명을 해주었고 간단한 3차원 DP 점화식을 제시하였다.
  • 그 사이에 D를 살짝 더 수정하여 제출하였고 WA가 나왔다. (D WA ?min)
  • 풀이를 들어보니 내가 생각한 점화식과 같았고, deuslovelt가 구현하여 맞췄다. (K AC 117min)

120 ~ 150min

  • hojoon0205가 L번 문제에 대하여 세운 가설의 반례를 찾았고 D가 많이 풀리고 있는 상황이라 일단 D를 함께 고민하기로 하였다.
  • 기존의 점화식에서 조건식을 약간 변형하여 동적 세그먼트 트리를 생성하면 $O(N\log{}N)$ 으로 시간을 줄일 수 있지만 0.4초라 안될 것 같다는 결론이 나왔다.
  • 나와 hojoon0205가 함께 고민하는 것으로 진전이 없을듯 하여 인원 조합을 바꿔서 고민하기로 결정하였고 deuslovelt에게 지금까지의 풀이를 설명해주었다.
  • 얼마 지나지 않아 동적세그를 사용하지 않고 좌표 압축과 함께 펜윅으로 똑같은 연산이 가능하다고 deuslovelt가 풀이를 제시하였다.

150 ~ 180min

  • 풀이를 듣고 내가 D번 코딩을 시작하였고 맞출 수 있었다. (D AC +2 160min)
  • 내가 코딩을 하는 동안 hojoon0205와 deuslovelt가 dfs 스패닝트리로 L을 접근하였고, 앞서 세운 가설과 풀이를 조합하면 정해가 나옴을 증명하였다.
  • L을 hojoon0205가 기존의 작성한 코드에 dfs 스패닝트리 부분을 추가하여 코딩하였고 맞췄다. (L AC +1 178min)

180 ~ 240min

  • 남은 문제는 정말 최상위권 팀들만 풀어낸 상태였고, 일단 각자가 읽은 문제와 아이디어를 모두 공유하는 식으로 결론이 나왔다.
  • 풀린 팀수와 전반적인 문제를 읽어본 결과 A와 C가 그나마 도전해볼만 하다고 생각하였고, deuslovelt가 A를 나와 hojoon0205가 C를 잡았다.
  • A번 문제에 대하여 deuslovelt가 그런디 넘버를 이용하여 풀 수 있을 것 같다는 아이디어를 제시하였고, 나는 해당 내용을 공부해본적이 없어 hojoon0205가 검증을 위해 함께 고민하기로 하였다.
  • 그러는 동안 C를 내가 혼자 고민해보았고, 삼각형으로 분할을 하는 것이 첫 접근이 될 것이란 추측 이외엔 별다른 풀이가 보이지 않았다.
  • 그런디 넘버가 맞는거 같다는 결론이 나왔고, 시간 복잡도는 고려하지 않고 일단 컴퓨터가 비었으니 deuslovelt가 코딩을 하기로 하였다.
  • 다시 나와 hojoon0205가 C를 고민하였고, 내부에 점이 없는 삼각형과 딱 1개 있는 삼각형을 알아야할 것 같다는 내 접근에 대하여 오목 사각형도 내부에 점이 없는 삼각형 2개로 보는 것이 더 쉬울 것 같다는 hojoon0205의 의견이 나왔다.
  • 둘 다 $O(N^4)$ 이하의 시간으로 내부에 점이 없는 삼각형을 판별하는 것에 집중하였고, 변 하나를 고정한 이후 점들을 정렬하는 식의 접근을 생각해보았다.
  • hojoon0205가 기준 변의 양 끝점에 대하여 정렬을 하고 투포인터 식으로 위쪽과 아래쪽에 위치한 내부에 점이 없는 삼각형의 개수를 세는 방법을 제시하였고 총 $O(N^3\log{}N)$ 이란 결론이 나왔다.
  • 하지만 정렬을 4차례나 하는 문제가 있었고, 일단은 C가 더 가망이 있을듯 하니 코딩을 해보자고 하였다.

240 ~ 270min

  • 컴퓨터를 넘겨받은 hojoon0205가 코딩을 하였고 TLE가 나왔다. (C TLE ?min)
  • 벡터를 배열로 바꾸는 마이너한 최적화를 더 넣어봤지만 여전히 TLE가 나왔다. (C TLE ?min)
  • 아무래도 $O(N^3)$ 으로 줄여야 한다는 생각이 들었고, 다시 나와 고민을 하고 컴퓨터는 deuslovelt가 넘겨받아 A를 짰다.
  • 나는 이전의 정렬 상태를 유지하면서 약간의 swap으로 새로운 정렬된 배열을 만들 수 있는지 식으로 접근해보았고 잘 되지 않았다.
  • 이때 hojoon0205가 정렬을 굳이 매번 할 필요 없이 미리 N개의 기준점에 대하여 정렬을 전처리하는 식으로 접근하여 $O(N^3)$ 풀이를 제시하였다.
  • A번의 경우 시간초과에 대한 확신이 없는 상태였기에 C에 일단 올인하자는 결론이 나왔고 hojoon0205가 풀이를 고치기 시작하였다.

270 ~ 300min

  • 기존의 코드를 많이 수정해야되는 상황이고, 기하 문제인 만큼 코딩이 까다로운 문제인 만큼 예제 데이터에서 답이 안나오는 문제가 발생하였다.
  • 가장 작은 예제 데이터로 디버깅을 진행하였고, 잘못된 부분을 찾아 고쳤고 AC가 나왔다. (C AC +2 291min)
  • 남은 9분은 밑져야 본전이란 마인드로 deuslovelt가 짜고있던 A를 계속 제출해보았고 WA와 TLE가 나오면서 결국 풀지는 못했다.

총평

마지막 10분전에 8솔브를 달성하면서 본선 수상을 확실하다고 생각이 들었고, 상위권으로 예상되는 팀들의 풍선을 봐도 충분히 14등 안에는 가능할 것으로 보였다. 실제로 스코어보드가 공개될 때, 잘하면 9등으로 동상도 가능하지 않을까라는 기대를 했지만 생각보다 프리즈 사이에 많은 팀이 8솔브를 달성하였고 전체 11등으로 마무리하였다. 추가적으로 8솔브가 본선 수상컷이 된 것을 보고 예전보다 참가자의 수준이 많이 높아졌다는 생각도 들었다.

비록 처음 팀을 결성할 때 목표로 세운 대학 순위 3~4위는 달성하지 못했지만, 나로서는 첫 메이저 대회 (UCPC, SCPC, ICPC) 수상이기도 해서 상당히 뜻 깊은 대회이다. 마지막 문제 코딩을 할 당시에 올해 UCPC 본선때 내가 마지막 15분에 코딩을 하였고, 당시에 압박감을 이기지 못하고 결국 풀지 못했던 기억이 있어 정말 간절하게 팀원을 응원했던 것 같다. 다행히도 UCPC보다 더 큰 무대인 ICPC 본선에서 압박감을 이겨낸 hojoon0205가 정말 대단하다고 생각하고, 내가 막혀있던 부분을 잘 해결해준 deuslovelt도 너무 훌륭했다. 사실 개인적으로 이번 대회에서의 역할만 놓고보면 아쉬운 점이 몇 가지 남는다. 여름방학에 공부해야지 하고 미뤄둔 그런디 넘버 관련된 내용을 공부하지 않아 A번 문제에서 deuslovelt에게 도움을 주지 못한 것과 D번 문제에서 펜윅+좌표압축 최적화를 빠르게 떠올리지 못한 점 이렇게 2가지가 아쉽다. (특히 D번의 경우 평소 연습 때 팀에서 내가 해왔던 역할인 만큼 더욱 아쉽다.) 그래도 1년 동안의 대장정의 마무리가 ICPC 본선 수상이라는 결실을 맺을 수 있게되어 다행이라 생각한다.

사실 올해 대회를 준비하면서 굵직한 대회 수상실적을 내지 못하면 어떡하지라는 불안감이 있던 것도 사실이다. 하지만 올해 ICPC에서 수상을 하면서 한동안은 PS에 관련된 고민은 접어두기로 했다. 1년 동안 매주 함께 모여 팀연습을 한만큼 한동안 종강하기 전까지는 연습이 없는 주말이 약간의 공허함으로 다가올 것 같기도 한다. 내년에는 hojoon0205가 졸업을 하면서 새로운 구성의 팀이 되겠지만, 팀원들과 함께 매주 연습하면서 많이 성장할 수 있어 좋았고, 무엇보다 뛰어난 팀원들과 1년 동안 함께할 수 있어 영광이었다고 전하고 싶다.

링크

문제
스코어보드