2022 ICPC Seoul Regional 본선 후기

팀 순위 8등, 학교 순위 4등으로 동상 수상했습니다.

어제부터 아무것도 올리지 않았는데 블로그 조회수가 높게 찍혀 최대한 빨리 후기를 써야겠다는 생각이 들었습니다. 하고 싶은 말이 많지만, 아래에서 하나씩 천천히 하겠습니다. 예선 후기는 아래 링크를 참고해주세요.

 

예선 후기 : https://leo630.tistory.com/123

 

팀 소개

저희 팀에서 저를 제외한 팀원 2명은 OI를 거의 하지 않았고, 저야 뭐 OI를 오래 하긴 했지만 잘한 것도 아니고 혼자 조용히 오래 한 것이라 아는 PS러가 많이 없습니다. 팀원 모두 PS 커뮤니티 활동도 잘 하지 않기 때문에 이 팀이 뭐하는 팀인지 모르시는 분들이 많을 것이라 생각합니다. 생각해보니 특별히 팀 소개를 한 적도 없는 것 같아 팀 소개를 먼저 하려 합니다.

 

slah007 (solved.ac, Codeforces, AtCoder) : 팀 내에서 수학과 기하에 가장 강합니다. 다만 디테일한 예외 처리에 약하며, 구현량이 많아지면 헤메는 일이 많습니다. 컨디션에 따라 퍼포먼스 차이가 많이 나는 편입니다. 00입니다.

qjatn0120 (solved.ac, Codeforces, AtCoder) : 팀 내 유일 레드 경험자인 만큼 코포, 앳코더를 쳤을 때 평균 퍼포먼스가 가장 좋습니다. 구현 속도가 빠르진 않지만 팀 내에서 가장 구현력이 좋기에 구현 문제를 자주 맡습니다. 관찰이 필요한 문제에 강하지만 수식 전개가 길어지면 힘이 떨어지는 편입니다. 가끔 사풀을 확신한 채로 내는 경우가 있어 대회가 망한 적이 몇 번 있습니다. (2021 ICPC D, 2022 UCPC C) 01입니다.

leo020630 (solved.ac, Codeforces, Atcoder) : 저입니다. 풀이를 아는 문제(보통 골드 이하)를 미는 속도가 팀 내에서 가장 빠릅니다. 딱히 강하거나 약한 분야는 없는 것 같습니다. 주로 말리는 패턴은 문제를 너무 어렵게 생각하거나, 한 가지 관찰에 꽂혀 다른 풀이를 생각하지 않는 경우입니다. 팀 내에서 백준 문제 수와 티어가 가장 높은 만큼 비교적 어려운 알고리즘들을 많이 접해보았습니다. 02입니다.

 

팀 연습은 올해 다 합치면 10번 넘게 진행했습니다. 팀 연습을 통해 팀 전략을 찾았다기보다는 각자의 특징을 파악할 수 있었던 것 같습니다. 팀 전략은 크게 없고, 그냥 (읽고 다른 사람이 더 잘 풀 것 같으면 주기),  (WA 받았는데 코딩 큐가 밀려 있으면 프린트하고 바로 넘기기)로 총 2가지 규칙 정도만 정하고 대회에 들어갔던 것 같습니다.

 

팀원 모두 백준을 열심히 풀기보다는 코포, 앳코더 등의 대회 참가를 통해 주로 연습했습니다. 따라서 팀 평균 레이팅도 꽤 높은 편이었습니다. 제가 옐로를 찍은 이후부터는 웬만하면 3오렌지 & 3옐로를 유지했고, 지금 코포 평균 레이팅은 2200을 좀 넘는 것 같습니다. 그럼에도 대회를 나갈 때마다 (2021 ICPC, 2022 UCPC) 대차게 박아버려서 팀원 모두 약간 자신감이 떨어져 있던 상태였습니다. 하지만 수상을 못할 실력은 아니라고 생각했기 때문에 수상권인 14위 안에 드는 것을 목표로 대회에 참가하게 되었습니다.

 

대회 전 - 11/18 (금)

저희는 학교가 포항에 있기에 예비소집에 참여하려면 꽤나 빨리 출발해야 했습니다. 포스텍의 다른 참가팀인 CRYPKlNG팀과 함께 9시 30분쯤 서울로 출발했습니다. 이랬음에도 여러 이슈 탓에 시간이 빠듯해 예비소집이 끝나는 5시까지 한 끼도 먹지 못했습니다. 예비소집 문제는 작년 리저널 B, D, L이었습니다. 그냥 각자 한 문제씩 풀었습니다. 에디터는 모두 CodeBlocks를 써서 세팅할 것은 많이 없었는데, 터미널에서 복붙이 제대로 안되는 점과 키보드가 너무나도 불편하다는 점이 좀 신경쓰였습니다. 다행히 복붙 문제는 구글링을 통해 잘 해결했고 키보드는 어차피 자리가 바뀌니 괜찮았습니다. 이후 몇 되지 않는 아는 팀인 DGIST의 SudaL 팀과 저녁식사를 한 후 헤어졌습니다.

 

대회 당일 - 11/19 (토)

8시 50분쯤 모든 팀원이 모였습니다. 대회 시작 전까지 딱히 한 것은 없고, 터미널 세팅법을 외운 후 우리 팀답게 이상한 소리나 하다 들어갔던 것 같습니다. 팀명에 맞게 slah007선배가 ABCD, qjatn0120선배가 EFGH, 제가 IJKL을 보고 시작했습니다.

 

~0:07

I를 봤는데, 코포에서 비슷한 문제를 본 적이 있어 바로 풀이가 떠올랐습니다. 세팅을 마친 qjatn0120선배에게서 바로 컴퓨터를 넘겨받은 후 예제가 나와서 냈더니 AC를 받았습니다. AC 색이 좀 이상해서 스코어보드를 봤더니 퍼솔이었습니다. I가 4n+1번째라서 다 I부터 풀었을 것 같았는데 퍼솔이라 기분이 좋았습니다. 그뿐만 아니라 제 블로그를 보신 분들은 아시겠지만 제 개인적으로 2021 ICPC-2022 UCPC-2022 ICPC 예선에서 모두 0솔을 해버렸기에 그냥 1솔 자체가 되게 후련했던 것 같습니다. 이후 F와 J가 풀렸길래 qjatn0120선배가 F, 제가 J를 잡았습니다.

 

~0:11

J는 I보다도 쉬웠습니다. 쉽게 짜서 AC를 받았습니다. 이후 qjatn0120선배가 F가 풀린다고 해 컴퓨터를 넘겼습니다.

 

~0:22

잘은 모르지만, F도 빠르게 맞았습니다. 이 때까지 1번도 틀리지 않고 3문제를 모두 굉장히 빠르게 풀었기 때문에 스코어보드에서 1등을 찍으며 혼란을 줄 수 있었습니다. 풀린 문제를 따라갈 수가 없어 잠시 당황했지만, 각자 쉬운 문제를 찾아 다시 떠났습니다. slah007 선배는 D를 계속 잡았고, 저는 K, qjatn0120 선배는 E를 읽었습니다.

 

~0:51

서로 E,K를 읽은 저와 qjatn0120 선배가 서로 바꿔 읽는 것이 무조건 이득이라는 것을 깨닫고 바꿔서 읽었습니다. K 풀이가 먼저 나왔고, qjatn0120 선배가 바로 짰지만 TLE를 받았습니다. 코드를 슬쩍 보니 탑다운 DP를 바텀업으로 바꾸면 될 것 같아 이를 지적해주었고, 다시 짜서 맞았습니다.

 

~1:15

K가 코딩되는 동안 E 풀이를 열심히 생각했습니다. 다익스트라로 대충 될 것 같아 K가 맞은 후 컴퓨터를 넘겨받았는데, 생각해보니 정점이 100N개라 잠시 당황했습니다. 다행히도 10N개의 정점만 사용하는 풀이를 바로 찾을 수 있었고 예제가 나와서 제출했으나 틀렸습니다. 다행히 반례가 u=w인 간단한 경우라 바로 고쳐서 AC를 받을 수 있었습니다.

 

~1:36

이후 D가 많이 풀렸길래 slah007선배한테 설명을 들었습니다. DP식 자체는 다 구했는데, 처리를 어떻게 할지 고민중인 상태였습니다. 다행히 qjatn0120선배가 그냥 pq로 하면 됨을 알아냈고 구현해서 맞았습니다.

 

~2:26

이후 전 A, slah007선배는 C, qjatn0120선배는 L로 넘어갔습니다. 가장 먼저 풀이가 나온 문제는 L이었습니다. qjatn0120선배가 비둘기집의 원리를 이용한 관찰을 빨리 해냈습니다. 구현량이 좀 있어 컴퓨터를 꽤 잡은 후에 한번에 AC를 받았습니다.

 

~3:49

qjatn0120선배가 L을 짜는 동안 저는 A에서 여러 관찰을 해두었습니다. 카드를 하나 지우면 그 열의 state가 0/1로 변한다는 점을 L을 다 짠 qjatn0120선배에게 설명했는데, qjatn0120선배가 듣자 마자 "그거 그냥 분할되는거 아님?"라고 하셔서 바로 풀이를 깨닫고 코딩에 들어갔습니다. 코딩 스펙도 어느정도 생각을 해 두었기에 코딩 시간은 얼마 걸리지 않았고 바로 예제가 나와서 제출했지만 WA를 받았습니다. DFS를 다르게 돌려야 하는 줄 알고 여러번 고쳤지만 결국 qjatn0120 선배가 찾아준 오류는 x와 y를 헷갈렸던 것이라 상당히 머쓱했습니다.

 

~5:00

이후 C를 푸는 데에 집중했습니다. 저는 문제를 보자마자 작년 예선 L번의 확장이라는 것을 깨달았지만, 슬프게도 해당 문제의 풀이를 몰랐습니다. 서울 리저널의 최근 출제 동향을 생각했을 때 복습을 했어야 했는데 그러지 못한 점이 아쉬웠습니다. slah007 선배가 삼각형까지의 풀이까지는 만들었지만 아쉽게도 사각형으로 발전시키기 위해서는 한 부분이 더 필요했고 그 부분을 짜다 대회가 끝났습니다. 

 

문제별 후기

티어는 추측입니다.

 

A (P1~2, solved by leo020630, qjatn0120) : 어려운 그런디+DP 문제이다. 풀이 자체는 무난히 찾았는데 구현 실수 탓에 약간 말렸다. 카드 하나를 지우면 게임판이 나누어지므로 DP를 통해 각 상태의 그런디 수를 구해주면 된다. 제한이 매우 작아 대충 짜도 되는 것 같다.

B (?, Not solved) : 4시간쯤에 읽었는데 너무 어지러웠다. 이걸 푼 팀이 있다는 사실이 더 어지럽다. 너무 멋있다.

C (D4~5, Not solved) : 작년 예선 L 풀이에서 각도 정렬로 볼록사각형과 오목사각형을 구분해주면 된다. 

D (P3~4, solved by slah007, qjatn0120) : DP 식을 정리하면 minimum range query 같은 것이 나오는데, 비교값이 단조적이라 그리디하게 처리해줄 수 있다.

E (P4~5, solved by leo020630) : 다익스트라 응용문제이다. 간선을 정점으로 생각한 후, 이상한 조건에 의해 구현을 쉽게 해주면 된다. 코너 케이스 하나가 있는데, 비교적 찾기 쉽다.

F (G?, solved  by qjatn0120) : 유일하게 정확히 모르는 문제이다. 그림이 KOI 개구리 점프와 비슷하게 생긴 것만 봤다.

G (?, Not solved) : 역시 4시간쯤에 읽었다. 엄청 어렵다.

H (?, Not solved) : 4시간쯤에 읽었다. Suffix Array로 무언가 한다는 것만 대충 유추 가능했다.

I (G4~5, solved by leo020630) : 팰린드롬임을 판별하기 위해서는 양 끝의 숫자를 반복해서 비교해주면 된다. 이를 응용해 다르면 한 쪽을 제거하면 다른 문자가 나올 때마다 분기가 2배로 늘어난다. \(k \leq 3\)이므로 분기는 최대 8번까지만 생기므로 이를 이용해 문제를 해결할 수 있다.

J (S2~3, solved by leo020630) : 그림과 예제를 통해 풀이를 유추하기가 쉽다. 괄호 문자열에 익숙하다면 쉽게 문제를 해결할 수 있을 것이다. 실제로 모든 팀이 해결하였다.

K (G3~4, solved by qjatn0120) : 문제를 읽다 해석이 잘 안돼서 qjatn0120 선배에게 넘겼다. LCS 비슷한 DP라고 한다.

L (P2~3, solved by qjatn0120) : 간선이 \(2N-3\)개이다. 일단 연결 요소가 하나라고 가정하면 \(N-1\)개로 스패닝 트리를 만들고 남은 간선은 \(N-2\)개이다. 가능한 사이클의 길이가 3부터 \(N\)으로 \(N-2\)개이니 겹치는 길이의 사이클이 있거나, 모든 길이의 사이클이 1개씩 있는 경우로 나뉜다. 후자의 경우를 보면 길이가 \(N\)인 사이클이 존재하니, 이 사이클을 만들고 남은 \(N-3\)개의 간선을 추가하는 식으로 생각해줄 수 있다. 여기서 간선을 하나 추가할 때마다 사이클이 2개씩 새로 더 생기고, 가능한 사이클의 길이는 3부터 \(N-1\)으로 \(N-3\)개이다. 사이클이 2개씩 생기니 비둘기집의 원리에 의해 겹치는 사이클이 무조건 존재한다.

대회 결과

위 스코어보드에서 볼 수 있듯이 전체 8등, 대학 기준 4등으로 대회를 마쳤습니다. 목표였던 14등을 훨씬 뛰어넘은 성과입니다. 여러 요인이 겹쳐 저희 팀이 낼 수 있는 퍼포먼스의 최대치를 냈다고 생각합니다. 제가 쉬운 부분인 IJKL을 받아 아는 문제를 최대한 빠르게 밀었고, qjatn0120 선배는 중간 난이도 문제인 A, D, L 풀이를 거의 바로 내 페널티 관리가 역대급으로 잘 되었습니다. 지금까지의 대회를 망쳐온 스케줄링 관리까지 너무 잘 했습니다. C까지 풀었다면야 더할 나위가 없었겠지만 그랬더라도 높은 경우로 상격과 대학 순위가 변하진 않았기 때문에 괜찮은 것 같습니다.

 

사람 마음이 참 야속한 것이, 상만 받자고 마음먹고 들어갔음에도 불구하고 막상 상황이 너무 잘 풀리니 중간에는 월파 욕심이 잠깐 나기도 했습니다. 하지만 저희 팀에게 이점이 된 부분은 NLP팀에게도 상당한 이점이었던 것 같고, 대부분의 시점에서 대학 순위 4위를 유지했습니다. 결국 마지막 순간에 C를 못 풀고 8개인 NLP팀의 풍선을 볼 때는 너무 아쉬웠지만 까보니 9솔이시길래 오히려 마음이 후련해졌습니다. 올해는 설카를 제외하고도 다른 대학들 전력이 다 강했기 때문에 현재는 만족 그 이상입니다.

 

그래도 이것저것 찾아보니 월파 갈 확률이 매우매우 낮지만 0은 아닌 것 같습니다. 티켓 개수 기준도 명확하지 않을 뿐더러 내년은 코로나 때문에 월파 2개가 한번에 열려 팀 선발 규칙도 예외적이라고 합니다. 그냥 잊고 살다 연락이 오면 로또 당첨이라고 생각하겠습니다.

 

후기

성불했습니다. 제 성불이기도 하고, 저희 팀의 성불이기도 하고, 포스텍의 성불이기도 합니다. 우선, 대학오고 탄 상이 버스로 받은 작년 UCPC 4등상과 논란의 중심인 현대모비스밖에 없었을 뿐더러 앞서 말했듯 중요 대회에서 0솔만 하던 저에게는 1인분 이상 하면서 최고의 결과를 거두었기 때문에 매우 기쁩니다. 저희 팀에게도 21 ICPC-22 UCPC를 정말 많이 망친 후 처음으로 팀이 실력대로 대회를 쳤기 때문에 다들 만족하는 것 같고, 포스텍에게 있어서도 6년만의 상이라 굉장히 뜻깊다고 생각합니다.

 

포스텍은 우선 기본적으로 학교에 사람이 많이 없고, PS를 하는 사람은 더더욱 드뭅니다. 다른 이공계 분야에서 학교가 가지는 이름값을 생각하면 정말 신기한 현상입니다. 물론 구전에 의하면 ICPC에서 금/은상을 받던 시기도 있다는 것 같지만, 어쨌든 전설로 생각될 만큼 예전의 일이고 결국은 월파 진출 0회에 최근 5년간은 ICPC 무상인 학교임이 현실이었습니다. 현재 레드 코더인 Hyperbolic 선배가 있었음에도 이러한 성적이었다는 점을 생각해보면 포스텍에게 있어 ICPC가 얼마나 불운의 연속이었는지 알 수 있습니다. 그래서 더더욱 올해 ICPC가 중요했습니다. 우선 저희 팀원 두 분은 현재 4학년이기에 이번 ICPC는 이 팀으로 나가는 마지막 대회였습니다. 앞서 말했듯 포스텍에서 3오렌지 팀이 나오기는 정말 힘든 일이고, 연습까지 열심히 했는데도 성과가 나오지 않았다면 정말 슬펐을 것 같습니다. 다행히도 좋은 퍼포먼스로 수상함으로써 성불에 성공했습니다. 뭐 당장 내년 대회부터는 1옵션이 되어야 한다는 생각에 좀 어지럽긴 하지만, 그래도 이제 가벼운 마음으로 대회에 나갈 수 있을 것 같습니다. 혹시 이 글 보시는 PS 잘하는 고등학생 분들은 포스텍도 적극 추천합니다. 좋은 학교에요..

 

저희 팀 외적으로는 처음 가보는 대면 리저널이었기에 좋았습니다. 회의실에 깔린 컴퓨터를 보고 진짜 뭔가 대회 치는 느낌이 들었던 것 같습니다. PS 대회는 역시 대면으로 하고 풍선도 받아야 맛이 사는 것 같아요. 대회장에서 일방적으로 아는 멋있는 분들도 많이 보았지만, 인사는 하지 못했습니다. ㅎㅎ.. 다음에 혹시 보시면 말 걸어주세요.. 다행히도 쌍방으로 아는 분들에게는 조금이나마 인사를 했습니다. 몇 가지 아쉬운 점이 있었다면 개인 키보드 지참 관련한 공지가 없었다는 점(다행히 저희가 대회 당일에 쓴 키보드는 괜찮았지만, 제공하는 키보드 중 키감이 심하게 구린 키보드가 있었던 것 같습니다), 대회 중 스코어보드를 앞에 띄워주지 않아 바로바로 확인하기 살짝 불편했던 점 등이 있었습니다. 하지만 큰 문제도 아닐뿐더러 대회를 잘 쳤기 때문에 별 생각은 없습니다.

 

1년 반동안 함께해준 팀원 두 분, 팀연습 같이 한 포스텍 다른 팀들, 그 외 모든 분들께 감사합니다.

이상으로 후기를 마칩니다.

 

올해를 관통하는 최고의 명언