The 2024 ICPC Asia Pacific Championship 후기 - (3)

서론

The 2024 ICPC Asia Pacific Championship 후기의 마지막 글입니다. 3부는 팀 소개와 본 대회 후기에 관한 내용입니다. 본 대회 후기는 평소에 쓰던 그것이고, 팀 소개에 앞서 한 가지 이야기를 더 할 예정입니다. 포스텍이 22년 서울 리저널 대회부터 좋은 성적을 계속 거두고 있지만 제 블로그 정도를 제외하면 정보를 얻을 곳이 하나도 없이 외부와 단절되어 있는 느낌이 있습니다. 따라서 궁금해 하셨을 분들이 많았을 텐데 이 글에서 좀 다루어보려 합니다. 제 개인적인 의견이 다수 포함된 글이 될 예정이므로 감안해서 읽어주시면 감사하겠습니다.

 

1부 링크 : https://leo630.tistory.com/211

2부 링크 : https://leo630.tistory.com/212

 

포스텍과 PS

포스텍은 다른 여러 분야에서 종합적으로 높은 평가를 받고 있는 대학이지만 최근 한동안 PS에서만큼은 유난히 약한 모습을 보여왔습니다. 이유야 여러가지가 있습니다만, 가장 큰 이유는 포스텍의 대입 정책이라는 것이 정설입니다.

 

우선 PS판은 고등학교때 잘하던 사람들이 대학 가서도 좋은 성과를 거두는 비율이 유의미하게 많습니다. 아무래도 대학 와서 PS를 처음 시작하는 것은 시간적으로도 여유롭지 못하고, 입문 장벽도 비교적 높기 때문입니다. 따라서 PS 공부를 열심히 한 고등학생들이 얼마나 오느냐가 그 대학의 ICPC 성적에 큰 영향을 미치는데, 포스텍은 이 부분에서 의외로 불리합니다.

 

가장 큰 이유는 서울대와 카이스트의 존재입니다. 슬픈 이야기이지만 대학 입시에는, 특히 과학고/영재고의 경우에는 각 대학에 대한 대강의 커트라인이라는 것이 존재하며 학생들은 이를 바탕으로 대입을 준비합니다. 그리고 포스텍을 지원하는 학생들은 서울대와 카이스트를 모두 후보군에 넣고 입시를 치르는 경우가 대부분입니다. PS판에서 이 두 대학의 위상은 두 말 할 것 없을 정도로 높습니다. 많은 국가대표 출신 학생이 진학하는 곳도, 서울 리저널의 우승 대학도, 더 나아가 World Finals 메달이라는 업적을 이뤄내는 곳도 대부분 저 두 대학 중 하나로 귀결됩니다. 따라서 PS를 공부한 고등학생이라면 여러 대학의 합격증을 받았을 때 저 두 곳으로 마음이 향하는 것이 당연합니다.

과학고/영재고 출신의 경우 위의 이유로 포스텍에 진학하는 경우가 드뭅니다. 그렇다면 남은 것은 일반고/특성화고에서 PS를 열심히 공부한 학생들인데, 일반계 고등학교에서 PS와 내신 공부를 병행하는 것은 상당히 힘든 일입니다. 그렇다면 서울권의 여러 대학처럼 특기자 전형이 운영되어야 하는데 그렇지도 않습니다. 따라서 이 역시도 일어나기 꽤나 힘든 일이 됩니다.

 

그래서 포스텍의 PS 생태계는 조금 기형적으로 돌아갑니다. 위에서 불평불만을 늘어놓긴 했는데 빈도가 적다 뿐이지 확률이 0은 아니라서 가끔 PS에 관심을 두던 학생들이 들어옵니다. 저처럼 학교 공부를 열심히 안 했거나, 여튼 다른 여러 이유로 포스텍을 선택한 고마운 사람들입니다. 그리고 이런 사람들이 총대를 매고 머리는 좋은데 PS에 관심 없는 사람들을 강제로 끌고 와 열심히 연습시킵니다. 이 과정은 가르치는 사람과 배우는 사람이 모두 힘들고 성공률도 정말 낮습니다. 허나 학교의 이름값이 허상은 아니었던 것인지 이전까지는 이러한 방법이 먹혔던 것 같습니다. 아마 2016년도까지는 리저널 스코어보드 상단에서 이름도 자주 보이고, 월파까지는 아니지만 금/은상등의 성과도 이루었다고 들었습니다.

 

그러나 백준 사이트의 규모가 커지고 solved.ac가 생기는 등의 이유로 PS 인구가 많아지면서 이러한 전략이 잘 통하지 않았던 것인지 2017년부터는 눈에 띄는 성적을 받지 못했습니다. 사실 이때 학교 안 이야기는 제가 잘 모르는 부분이라 더 다루기는 힘들 것 같습니다. 당시 학부생이던 Hyperbolic 선배님의 말씀을 종종 듣는데, 아마 혼자 많은 것을 해야 하셨기에 부담이 크셨던 것 같습니다.

 

 

팀 결성 과정

위와 같은 상황에서 2021년도에 제가 입학했습니다. 그간 포스텍에서는 Hyperbolic 선배가 졸업하시고  두 19학번 선배  qjatn0120, slah007이 포스텍의 PS 동아리 POSCAT을 지탱하고 있었습니다. 다만 말이 좋아서 지탱이지, 가뜩이나 원래도 사람이 없는데 코로나까지 맞다 보니 PS 인구는 둘을 제외하면 없다시피 했습니다. 그나마도 20' 리저널을 둘이 다른 팀으로 나가는 기행을 벌이는 바람에 성적이 잘 나오지 않았습니다.

 

저도 고3 1년간 PS를 접었던 상태였고, 대학 가면 PS를 청산하고 새 인생을 살려던 참이었습니다. 그런데 막상 와보니 숫자도 딱 맞고, 선배들 실력도 좋고, 나 아니면 할 사람이 없어 보여서 그냥 복귀하기로 했습니다. 그렇게 000102 팀이 결성되었습니다. 21~22년도에는 21' UCPC를 제외한 모든 대회를 이 팀으로 나갔습니다. 센 팀이라고 생각했지만 22' ICPC 예선까지 모든 대회를 망쳤고, 다행히 22' 서울 리저널에서 매우 좋은 성적을 거두며 성불할 수 있었습니다. 되돌아보면 확실히 강한 팀이 맞아서 플레이오프가 1년 먼저 생겼다면.. 하는 생각을 아직도 가끔 합니다.

 

000102 팀에서 01은 졸업을, 00은 2년 후를 기약하며 군대로 떠났습니다. 저는 당장 은퇴나 휴식 계획이 없었기에 새 팀을 꾸려야 했습니다. 일단 한 명은 고르기가 편했습니다. kwoncycle이 그 주인공으로, 23년 초반을 기준으로 000102를 제외하면 유일한 퍼플 이상의 실력자였고 저와 강점도 달랐기에 빠르게 결정할 수 있었습니다. 

 

그리고 아무도 없었습니다. 사실 22년에서 23년으로 넘어갈 때는 이 점 때문에 그냥 1년 쉬어가는 해가 될 줄 알았습니다. 다행히도 교내 대회인 PPC에 블루 정도 되는 팀들의 경쟁이 치열했고, 여기서 팀원을 잘 골라보기로 했습니다. 그 중 가장 눈에 띈 것이 1년 후배인 petamingks였습니다. 상금을 타기 위한 각오였는지, 팀 내에 남은 1자리를 위해서였는지, 혹은 둘 다였는지 모르겠습니다만 1달만에 코포 200점을 올리며 퍼플에 입성했고 동시에 교내대회 우승까지 차지했습니다. 그렇게 팀원이 leo020630, kwoncycle, petamingks로 확정되었습니다. 여담으로 21-22-23년도 PPC 우승자라는 나름 어벤져스 비슷한 조합이기도 합니다.

 

팀 전략

비교를 위해 000102 팀부터 설명하자면, 이 팀의 전략은 다른 대부분의 ICPC 팀과 같았습니다. 흔히 말하는 3-solver 형태로, 각자가 문제를 읽고 풉니다. 뭐 어느 정도의 의사소통 후 문제를 넘기는 경우는 있었지만 이러한 경우가 큰 비중을 차지하지는 않았습니다. 팀원 모두가 ICPC 셋을 혼자 무리 없이 돌 수 있는 정도의 실력이라 가능했던 전략입니다. 단점으로는 각자 말렸을 때 도움을 청하는 빈도가 적어 복구가 좀 힘든 경우가 있었습니다.

 

허나 AllSolvedin1557 팀에서는 이러한 전략을 그대로 사용할 수 없었습니다. 그 이유는 간단합니다. 저를 제외한 두 팀원이 상위권 팀 기준으로 코딩을 너무 안 했습니다. 아래는 두 팀원의 solved.ac 그래프입니다.

 

수리검 듀오 담트와 찬트

 

물론 저정도로 심각한 상태는 아니고, 점수 달려있는 코포에서는 적당히 잘 풉니다. 그래도 팀원 간의 지식 격차가 작년과 비교했을 때 크게 벌어진 것은 사실이었고, 두 팀원이 물리적으로 손을 못 대는 문제들이 있었기에 3-solver 전략은 폐기해야 했습니다.

 

여기까지 보셨다면 저희 팀의 성적이 운빨, 혹은 원맨팀 아니냐는 의문을 가지실 수도 있습니다. 하지만 제가 혼자 월파를 갈 만큼 PS를 잘하지는 못하고, 두 번의 큰 대회 결과와 팀 연습 기록들이 저희의 퍼포먼스가 단순 운은 아니라는 것을 설명하고 있습니다. 그렇다면 뭔가 다른 요소가 작용했다는 것인데, 무엇일까요? 일단 저희는 팀 전략 덕분이라고 생각하고 있습니다.

 

실제로 팀 연습을 몇 번 하지 않은 상태인 서울 리저널에서는 대회 중에 이상한 짓을 정말 많이 했음에도 결과가 꽤 괜찮아서 모두가 연습에 대한 필요성을 느꼈습니다. 따라서 1월 말부터 집중 수련을 시작했습니다. 다행히 전략이 수정될수록 팀 연습 결과가 점점 좋게 나와 다들 기쁨, 그리고 한편으로는 대회 때에도 이처럼 해야 한다는 부담감을 동시에 느꼈던 것 같습니다. 그렇게 완성된 저희 팀 전략은 다음과 같습니다.

 

 

팀원 소개

 

leo020630 (solved.ac, Codeforces)

 

팀원 중 가장 정석적인 루트로 PS를 해왔습니다. 전반적인 코딩 속도가 셋 중 가장 빠르고 그래프나 자료구조 등의 웰노운 문제를 잘 풉니다. 또한 기하, 문자열, 플로우, 기타 팀노트에 있는 사전지식들을 혼자만 쓸 수 있습니다. 대신 케이스 워크를 심각하게 대충 하는 버릇이 있어 페널티 적립을 심심찮게 하고, 두 팀원에 비해 수학, 애드혹, constructive를 못 합니다.

 

외적으로는 팀연습 셋 고르기, 후기 쓰기, 타 팀과 소통하기 등의 짬처리를 도맡아 하고 있습니다.

 

kwoncycle (solved.ac, Codeforces)

 

MO 및 CTF 출신이며 PS는 거의 하지 않았는데, 1학년 때 제가 PPC를 쉽게 우승하는 것을 보고 나도 할 수 있겠다며 PS를 시작한 범상치 않은 인물입니다. 코딩이 느린 대신 케이스 워크나 증명을 꼼꼼하게 하는 편이라 팀 내에서는 더러운 구현 문제를 주로 가져갑니다. 그 외에도 CTF에서 크립토가 주 분야인 만큼 정수론이나 constructive, interactive에 강점을 가지고 있습니다. 자료구조나 그래프도 어느 정도는 짤 줄 아는데 팀 연습에서는 제가 풀이를 듣고 짜는 것이 빠르다는 결론을 얻어서 그 뒤로는 잘 하지 않았습니다.

 

외적으로는 멘탈이 잘 나가서 한 번 수틀리면 위에 써진 장점들은 없어지고 샷건을 연발하며 10번씩 제출을 하는 광인이 남는다는 점이 있습니다. 그 외에도 클래스 미는 것이 귀찮다고 자꾸 solved.ac 디스코드에서 골드 계정으로 채팅을 치는 등 저희 팀에서 금쪽이를 담당하고 있습니다. 팀명도 이 사람이 제안했습니다.

 

petamingks (solved.ac, Codeforces)

 

역시 MO 출신이며 PS는 수학 문제 위주로 풀다가.. 딱히 변한 것은 없고 아직도 수학 문제 위주로 풉니다. 파이썬으로 문제를 푸는 탓에 코딩 속도는 빠르지만, 시간이나 숙련도 문제로 못 짜는 문제가 너무 많아서 컴퓨터를 잡는 시간은 가장 짧습니다. 대신 관찰 면에서 큰 장점을 가지고 있는데, 문제 하나에 대해 여러 방향으로 접근할 수 있는 능력이 있어서 뭔가 중얼거리다 맞는 관찰을 해 오는 경우가 많습니다. 그렇게 관찰을 하고 나면 대부분은 저나 kwoncycle에게 던지고, 수학이나 DP인 경우 본인이 코딩합니다. 컴퓨터 밖에 있는 시간이 가장 많기에 스코어보드를 보고 오더를 하는 역할이기도 합니다.

 

외적으로는 하극상으로 날뛰는 kwoncycle을 제압하는 역할을 맡고 있습니다.

 

이렇게 보면 뭔가 나사가 빠져 있는 팀 구성이지만, 저희 팀의 장점은 셋이 문제를 푸는 방식이 모두 다르다는 점입니다. 굳이 정리하자면 저는 경험으로, kwoncycle은 증명으로, petamingks는 직관으로 문제를 해결합니다. 그리고 또 하나의 장점은 팀원간 의사 소통 및 역할 분배가 아주 잘 됩니다. 저희 팀의 운영 타임라인을 적어보면 대강 아래와 같습니다.

 

초반부 (시작 ~ 1:00)

 

각자 받은 부분에서 골드 이하 문제들을 찾아 풉니다. 쉬운 문제는 보통 먼저 본 사람이 풀지만 다익스트라 등의 그래프일 경우 제가, 구현 + 케이스 워크 문제일 경우 kwoncycle이 가져갑니다. petamingks는 쉬운 수학 문제를 빨리 골라 푼 후 이때부터 재미있어 보이는 플~다 문제와 씨름에 들어갑니다.

 

중반부 (1:30 ~ 4:00)

 

중간 난이도인 플래티넘 문제들을 하나씩 해결합니다. 보통 제가 2개 정도를 풀면 kwoncycle이 1문제의 풀이를 찾고, kwoncycle의 코딩을 기다리는 동안 저는 petamingks에게 풀이를 받거나 더 풀 문제를 찾습니다. 이 시간대에 petamingks가 컴퓨터를 잡기도 하는데 대부분 무시 가능한 정도의 시간입니다.

 

후반부 (4:00 ~ 5:00)

 

이제 풀 문제가 1~2개로 좁혀집니다. 이 시간대의 경우는 보통 두 케이스로 나눠집니다.

 

(1) 남은 문제가 petamingks, kwoncycle이 도움을 줄 수 없는 유형일 때

 

플레이오프가 이런 경우였는데, 두 팀원이 K에서 할 수 있는 것이 없었습니다. 이런 경우엔 제가 해당 문제를 어떻게든 풀고 두 사람은 적게 풀린 수학 문제를 공략합니다. 이번 경우에는 L을 두 사람이 같이 봤고, 풀이에 상당히 근접했지만 아쉽게 해결하지 못했습니다.

 

(2) 그렇지 않을 때

 

셋 모두가 달라붙어서 해당 문제 풀이를 논의합니다. 셋의 접근이 다 다르기에 생각을 공유하다 보면 맞는 말이 나오는 경우가 많습니다. 서울 리저널이 이에 해당했고, H번에 모두가 달라붙어서 결국 petamingks가 해결했습니다. 풀어야 하는 문제가 구현량을 요구하면 제가 풀이를 찾지 않았더라도 컴퓨터에 앉아서 조종하는 대로 코딩합니다.

 

한국의 다른 팀과 비교했을 때에는 전반적으로 서울대의 HLD 팀 전략과 비슷한 것 같습니다. 다만 제가 컴퓨터를 잡는 비중이 조금 더 작고, 남은 두 명이 분야를 더 가린다는 차이가 있습니다.

 

이런 전략을 사용했을 때 제가 생각하는 저희 팀의 장점과 단점은 아래와 같습니다.

 

장점

 

문제에 대해 다양한 방식으로 접근하며, 이에 대한 소통이 굉장히 익숙하기에 다이아 하위 이하 문제에 대한 풀이를 매우 높은 확률로 낼 수 있습니다. 따라서 초반에 조금 말리더라도 중후반에 이를 기반으로 복구할 수 있는 힘이 있습니다.

 

위 장점과 더불어 특별한 경우가 아니라면 스코어보드를 따라가는 운영을 기반으로 하기에 저점이 높습니다.

 

셋에 수학 문제가 많을 경우 팀원 모두가 제 역할을 할 수 있어 기대할 수 있는 고점이 높아집니다.

 

많은 팀 연습으로 인해 대회장에서 비효율적인 판단을 하는 경우가 드뭅니다.

 

단점

 

풀이 도출 능력에 비해 코딩 속도가 떨어져서 중간 난이도층이 두텁고, 구현량이 많은 셋에 약합니다. 실제로 팀 연습을 거듭할수록 풀이를 잘 내게 되어서 놀다가 끝난 경우보다는 마지막까지 코딩이 밀려 있던 경우가 많았습니다.

 

셋에 저만 풀 수 있는 웰노운 문제가 너무 많을 경우 제가 말리면 팀이 그대로 멸망합니다.

 

팀원 모두 다이아 상위 이상의 문제를 풀어본 경험은 잘 없어서 엄청나게 높은 고점은 기대하기 힘듭니다.

 

저희 팀을 요약하자면 합집합은 넓은데 교집합이 좁습니다. 따라서 서로가 서로의 영역을 쓸 수 있도록 의사 전달에 있어서 많은 연습이 필요했습니다. ICPC는 결국 팀 대회기에 팀의 전력을 높이는 것이 중요하고 그러기 위해선 합집합이 최대한 넓어야 합니다. 물론 모든 팀원이 모든 분야를 잘하면 좋겠지만 그런 팀을 만드는 것은 정말 어렵습니다. 따라서 ICPC 팀을 꾸릴 때 자신과 다른 성향의 팀원을 데려온 후, 합집합을 온전히 활용할 수 있도록 연습하는 것을 추천드립니다. 사실상 이 내용이 이 글을 쓰게 된 가장 큰 계기이기도 합니다.

 

본 대회 후기

위에서 하고 싶은 말들을 쓰느라 정작 이 글의 원래 목적인 본 대회 후기가 조금 묻히는 감이 생겼습니다. 사실 많은 분들이 궁금해 하신 내용은 위까지였을 것 같아서 본 대회 후기는 평소와 같은 양식으로 간단히 써 보겠습니다.

 

 

 

~0:00

평소에는 코딩이 가장 빠른 내가 컴퓨터에 앉아 시작하지만, CodeBlocks를 바로 사용하면 되는 나와 달리 둘은 VS Code 세팅이 필요했기에 kwoncycle이 이를 처리하기로 했다. petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:26

가운데 문제 중 H가 가장 쉬웠고, 마침 퍼솔도 나왔길래 H를 짰다. 아니나 다를까 예외 처리를 대충 해서 1번 틀리고 맞았다. 그 사이 petamingks는 C 풀이를 찾았다. 나한테 주려고 하길래 거절한 후 나는 kwoncycle이 던져준 J를 봤다.

 

~1:09

그 사이 C가 한 번 틀렸던 것 같은데, J 풀이가 나와서 치우고 열심히 짰다. 예제가 친절한 덕에 한 번에 맞았다. 이후 kwoncycle의 E 풀이가 나와서 두 문제를 동시에 코딩하기 시작했다.

 

~2:15

정말 정신이 나가버릴 뻔 한 시간대이다. 2시간까지 2솔 상태로 있었는데, E는 kwoncycle이라 코딩 자체가 오래 걸림 + 이상한 실수로 1번 틀렸고 C는 예외 처리가 계속 부족해서 petamingks가 컴퓨터를 잡았다 놨다를 반복했다. 이때 거의 40등대까지 내렸었던 것 같다. 나는 나라도 정신을 차려야 한다고 생각했고, G를 조금 보다 kwoncycle이 준 K로 갔다. K는 내가 아주 좋아하는 트리 비빔밥이라 다행이라고 생각했다. 풀이는 대충 이것저것 때려넣다 보면 나오는데, PST를 정말 오랜만에 짜는데다 팀 노트에서 뺀 유일한 내용이 PST였기 때문에 손코딩을 열심히 하고 들어갔다. 다행히 두 팀원이 E와 C를 연달아 맞아서 K 코딩에 들어갔다.

 

~3:04

상을 가져다 준 시간대이다. K를 열심히 짜고 있었는데 컴퓨터에서 나간 둘이 뭐라뭐라 대화하더니 G 풀이를 만들어왔다. 코딩이 짧다고 해서 바로 비켜주었더니 kwoncycle답지 않게 빠르게 짜서 1번에 맞았다. 그 동안 petamingks가 F를 읽자마자 가장 핵심적인 관찰인 소인수를 바로 떠올렸고 뒤의 스위핑은 내가 정말 빠르게 짤 수 있어서 G AC를 받자마자 들어가서 풀었다. 그 결과 어려웠던 두 문제인 G와 F를 고작 12분 간격으로 해결할 수 있었다.

 

~3:56

일단 풀이가 남은 문제는 K밖에 없었기에 다시 컴퓨터에 앉았다. 그러다 LCA를 찾는 부분을 약간 잘못 생각했다는 사실을 깨달았다. 이를 고치려면 오프라인에 세그를 하나 더 만들어야 했다. 해야만 하는 상황이었기에 이를 악물고 코딩했다. 다 짠 후 N=5, Q=25인 입력을 나오게 하기 위해 디버깅을 열심히 했고 잘 나오길래 제출했는데... RTE를 받았다. 배열 크기도 다 잘 잡았기에 당황했는데, 알고 보니 제출을 J에 했었다. 바로 다시 제출했고 채점이 꽤나 오래 돌아 안심했다. 다행히도 Accepted를 볼 수 있었다. 이때 손이 정말 바들바들 떨렸던 것 같다. 이후에는 L 사풀이 나왔다길래 바로 비켜주었다.

 

~5:00

이후에는 petamingks와 B를 봤지만 별 다른 소득을 얻지 못했다. 그러던 와중 kwoncycle이 L을 열심히 짰는데 반례가 안 나온다고 해 브루트 포스 코드를 짜 주었다. 다행히 반례는 찾았지만 풀이를 완성하지 못해 7솔으로 마무리했다.

 

문제별 요약

 

A (?, Not solved) : 대회 중에는 문제를 읽지 않았다. 정말 많은 케이스 분류를 요하는 문제인 것 같다.

B (D4, Not solved) : 마지막에 읽었는데 clique 크기의 bound를 충분히 줄이지 못했다. 이런 유형을 덜 풀어서인지 풀이를 들었음에도 잘 모르겠다. 업솔빙 예정

C (G1, solved by petamingks) : 구현이 까다로운 애드혹 문제이다. 대회 중에 petamingks가 좀 많이 틀렸다.

D (D3,  Not solved) : 대회 중에는 문제를 읽지 않았다. 까다로운 조합론 문제인 듯 하다.

E (G1, solved by kwoncycle) : 역시 애드혹 + 구현 문제이다. 들어 보니 케이스 워크가 좀 까다로운 것 같다.

F (P2, solved by leo020630, petamingks) : 그룹의 크기가 소인수이면 충분하다는 관찰을 하면 전형적인 스위핑으로 해결할 수 있다. 다만 이 관찰이 어려웠던 것 같고, 약수의 크기만큼 정직하게 돌리는 풀이는 TLE를 받을 텐데 많은 팀들이 여기 낚여서 시간을 허비한 것으로 보인다.

G (P4,  solved by kwoncycle, petamingks) : 풀이에 크게 관여하지 않았다. 비둘기집의 원리를 이용하면 짧은 코드로 해결할 수 있다고 한다.

H (S1, solved by leo020630) : 간단한 그리디 + 케이스 워크 문제이다. 틀리기 쉬운 예외 케이스에 낚여서 1번 틀렸다.

I (D3, Not solved) : 문제를 읽자마자 빠르게 건너뛰었다. 어려운 기하 문제이다.

J (P5, solved by leo020630) : 잘 알려져 있는 유형의 다익스트라 문제이다. 나는 조금 복잡하게 생각해서 다익스트라를 2번 돌리느라 코딩이 오래 걸렸다.

K (D5, solved by leo020630) : 우선 오프라인으로 해결하자. x를 찾는 것은 쉽고, LCA를 결정하는 것은 DFS 과정에서 각 서브트리의 크기를 저장하는 세그먼트 트리를 관리하면 된다. LCA를 결정하면 Y는 ETT를 이용해 구간에서 K번째 수를 찾는 연산으로 바꿀 수 있다. 이는 여러 방법이 있는데, 나는 PST를 사용하였다. 나중에 들으니 머지 소트 트리를 사용하는 로그 세제곱 풀이도 통과했다는 것 같다.

L (D4, Not solved) : kwoncycle이 대회 중에 열심히 시도했으나 결국 해결하지 못했다. 당시 코드에서 조금만 바꾸면 된다고 하는데, 알아채기 쉽지 않은 부분이라 막 아쉽지는 않다.

M (D1, Not solved) : 대회 중에는 문제를 읽지 않았다. 조합론 FPS 문제로 보이는데 풀어서 Hyperbolic 선배를 기쁘게 해 드리고 싶었으나 안타깝게도 그러기엔 너무 어려웠던 것 같다.

 

후기

작년 서울 리저널 후기 글에서 2번째 우승이니 3번째 우승이니 하면서 적어 놓은 말이 있습니다. 3번째 우승은 본인이 실력 있는 사람이라고 증명하는 것이라는 내용이었는데요, 사실 다른 월파 팀 구성원에 비해 제가 그렇게 실력 있는 사람이라고 생각하지는 않습니다. 그러나 운이 좋았고, 그냥 성실히 했던 보상을 좋은 팀원으로 얻었다고 생각합니다. 실제로 두 팀원 모두 대충 간접적으로 저 때문에 PS를 제대로 잡기 시작했으니 어느 정도는 맞는 말이기도 합니다.

 

사실 대회 결과에 대해서는 아직도 실감이 잘 나지 않습니다. 사실 대회 전에는 이에 대해서 정말 큰 부담감을 느꼈습니다. 애초에 기대가 낮았던 22~23년 리저널과는 달리 이번에는 월파 진출이라는 확실한 목표가 있었으며 목표가 멀지 않다는 것 또한 알았기에 모두가 극도의 긴장 상태에 있었습니다. 이 당시 심정은 이 글에 잘 나와 있습니다.

 

여튼 그래서 대회 가서도 여기가 베트남인지 어딘지 감각이 없는 상태였습니다. 일정이 너무 바쁘기도 했고, 특히 대회 당일에는 여기저기 끌려 다니느라 시상식 끝나고 나서야 좀 생각할 시간이 났던 것 같습니다. 막상 지금은 내가 월파에 나간 것이 맞나? 싶을 정도로 달라진 게 없는 것 같다가도 다른 방향의 미래를 생각할 때면 등골이 오싹해지며 감사함을 느낍니다. 월파는 일단 가는 것만으로 목표를 차고 넘치게 이룬 것 같아서 아마 카자흐스탄행 비행기를 탈 때는 되어야 비로소 체감할 듯 합니다.

 

또 운이 좋았던 점이 있다면 Asia Pacific Championship 대회 그 자체입니다. 사실 20~23년 리저널은 서울대/카이스트 뿐 아니라 숭실대 팀이 정말 강해서 서울 리저널에서 티켓을 따기가 어려웠는데, 정말 좋은 시기에 좋은 기회를 얻게 되어 다행이라고 생각합니다. 이 대회의 첫 수혜자로서 저희 팀이 월파 진출에 대한 입구를 조금이나마 넓힌 것 같아서 기쁩니다. 이 글이 조금이나마 도움이 되어 앞으로도 잘하는 한국 팀들, 그 중에서도 POSCAT 후배들이 공부를 열심히 해 좋은 결과를 이어나갔으면 하는 바람입니다. 사실 포스텍 최초 WF 진출 팀이 이런 팀명인 것에 상당한 책임을 느끼고 있어 더 나가주었으면 하는 생각이 있습니다.

 

Special Thanks To...

 

언급했지만 저희 팀이 좀 모자라서 도움을 주신 분들이 많습니다.

 

먼저 베트남까지 가서 대회 치느라 고생하신 한국 플레이오프 참가 팀들, 특히 1달간 팀 연습 러닝메이트로 달려주신 연세대 SCC와 Cookie 팀께 감사드립니다. SCC팀은 아직 티켓 수 발표를 기다려야 하는 것으로 알고 있는데 좋은 결과 있기를 정말 바라고 있습니다.

 

또한 동아리 내에서 도움 주신 Hyperbolic, menborong, slah007, qjatn0120 선배들, 그리고 다른 모든 부원들께 감사드립니다. 특히 qjatn0120 선배는 베트남에서 평소보다 조용한 모습으로 짐꾼을 자처하며 저희가 대회에만 집중할 수 있도록 해 주셨는데, 매우 감사하게 생각합니다. 또한 Hyperbolic 선배는 큰 이변이 없다면 카자흐스탄에 Co-Coach 자격으로 같이 가게 될 것 같습니다. 그때까지 잘 부탁드립니다.

 

마지막으로 저희 팀의 장점을 팀워크라 소개했지만 사실은 그냥 좀 시끄러운게 다입니다. 대회장 안에서 시끄러운 것이야 좋다고 생각하는데, 밖에서도 많이 떠드는 편입니다. 가끔은 이런게 팀인가 싶을 정도로 서로 열받게 하는 것이 일상인데 그래도 연습 대부분과 대회장 안에서만큼은 진지한 모습으로 1년간 함께한 PS계의 아주부 프로스트, kwoncycle과 petamingks에게도 감사의 말씀을 전합니다. 월파까지 6달 정도 남았는데 그동안 kwoncycle은 솔브닥 다이아부터 찍고, petamingks는 은퇴니 뭐니 하지 말고, 무엇보다 싸우지 말고 그냥 최대한 열심히 준비해 유종의 미를 거뒀으면 좋겠습니다.

 

2024 ICPC World Finals 후기로 찾아뵙겠습니다. 그간 응원해주신 분들, 긴 글 읽어주신 분들 모두 감사합니다.

 

-완-

 

같이 보면 좋은 링크

 

kwoncycle의 날것 후기 - https://kwoncycle.tistory.com/14

 

Teamwork in Programming Contests (hongjun7) - https://hongjun7.github.io/Teamwork_in_Programming_Contests.pdf