2023 ICPC Seoul Regional 본선 후기

 

11등, 해외 대학을 제외하면 10등으로 장려상 수상했습니다.

 

2023 ICPC Seoul Regional 본선에 출전했습니다. 대회가 끝난 후 다른 팀들 후기가 있나 구글링을 해 봤는데 올해 후기는 별로 없고 제 작년 후기가 가장 위에 뜨길래 올해도 빠르게 후기를 작성해보려 합니다.

 

2022 본선 후기: https://leo630.tistory.com/147

2023 예선 후기: https://leo630.tistory.com/191

 

대회 전

 

올해 ICPC를 함께 한 팀원은 kwoncycle, petamingks 입니다. 팀 결성 계기나 팀원 소개는 예선 후기에 어느 정도 써 두었기에 생략하겠습니다. 사실, 정말 간절한 마음으로 대회를 쳤던 작년과는 다르게 올해는 좀 느슨해져 있었습니다. 특히 SCPC가 끝나고는 더 그랬습니다. 그래서인지 PS를 작년처럼 열심히 하지는 않았고, 팀 연습 역시 몇 번 하기는 했지만 뭔가 제대로 된 적이 없어서 블로그에도 따로 올리지 않았습니다. 그러다 대회 일주일 전, 마침 몰려 있던 과제가 (그리고 롤드컵이) 모두 끝나 PS를 할 여유가 조금 생겼습니다. 일주일 동안 뭔가 대단한 연습을 하긴 힘들었고, 리저널 기출 복습과 팀노트 완성을 과정으로 삼아 30점 남았던 루비를 찍고 대회를 치기로 결심했습니다. 빨리 끝날 줄 알았지만, 30점이라는 점수가 생각보다 적은 것이 아니어서 결국 대회날 아침에 팀노트를 부랴부랴 참고해 루비를 찍을 수 있었습니다. 이 자리를 빌려 제 팀노트의 근간이 된 justicehui님과 koosaga님께 감사의 인사를 드립니다.

 

출처: 대회 당일 아침의 동아리 디스코드 / 답변이 인상적이다

 

여기까지는 제 개인적인 이야기였고, 팀적인 얘기를 해보겠습니다. 작년 팀의 경우 세 명이 모두 딱히 가리는 분야가 없고 실력적으로 큰 차이가 나지 않아 누가 코딩을 하던 크게 상관이 없었지만, 올해 팀은 그렇지 않아서 팀 전략이 더 필요했습니다. 구체적으로는, 올해의 경우 풀이를 내는 능력 자체는 팀원 간에 큰 차이가 없지만 사전지식이나 코딩 속도에 있어 제가 큰 우위를 가지고 있었습니다. 특히나 petamingks는 파이썬 사용자였기에 컴퓨터를 잡는 것이 큰 위험비용이라고 보았습니다. 따라서 많은 팀 연습을 필요로 했는데, 상술하였듯이 제대로 진행된 팀 연습이 많이 없었기에 대회 이틀 전인 목요일에 5시간 풀 연습을 하기로 했습니다. 포스텍의 다른 팀인 Con Energia와 함께 진행했으며, 셋은 2018 서울 리저널을 사용하였습니다. 

 

 

다행히, 어떻게 보면 사실상 첫 연습이었음에도 불구하고 상당히 괜찮은 결과가 나왔습니다. 당시로 치면 8등 정도 되는 성적이었는데, 여러가지 따질 부분이 있긴 했지만 이 연습을 계기로 상에 대한 생각을 조금씩 하게 되었습니다. 특히나 팀 전략에 대한 윤곽을 잡을 수 있었는데, 해당 연습에서 제가 7솔을 하긴 했지만 남은 두 팀원이 풀어준 문제가 C, E, J로 수식 컨트롤과 수학적 직관이 많이 필요한 문제였습니다. 반면에 제가 푼 문제들은 난이도가 쉽거나(D, F, L), 웰노운성인(A, B, J, K) 문제였기에 밸런스가 잘 맞았습니다. 최종적으로 저희 팀이 좋은 성적을 거두기 위해서는 제가 쉬운 문제를 정확하게 밀고, 남은 두 팀원이 어려운 문제를 (특히 수학을) 한 문제 정도씩만 풀어줘도 괜찮겠다는 결론을 얻었습니다.

 

그렇게 예비소집 날이 다가왔습니다. 작년 후기에도 언급했듯이 이동에 상당한 시간을 쓴 탓에 대회 당일에는 잠을 푹 잘 수 있었습니다. 인서울 대학 팀들은 일산이 멀다고들 하던데 저희는 잘 모르겠고 그냥 대전이나 포항이나 부산에서 열어주었으면 좋겠습니다.

 

대회 당일

kwoncycle이 앞, 제가 중간, petamingks가 마지막을 보고 시작했습니다.

 

~0:16

 

kwoncycle이 D가 쉬운 문제라고 해 컴퓨터 자리에 앉아 있던 저와 위치를 바꿨습니다. petamingks는 평소에 \(N\) 하나 주어지는 문제를 풀겠다고 한 사람답게 J에 꽂혀 있었고, 저는 지문이 짧은 F와 H를 먼저 읽었습니다. 조금의 구현 끝에 kwoncycle이 D를 한 번에 맞으며 산뜻하게 시작할 수 있었습니다.

 

~0:27

 

kwoncycle이 D를 짜는 동안 저는 스코어보드에서 많이 풀린 I를 읽었습니다. 증명은 하지 않았지만 대충 될 것 같은 풀이가 보여 바로 짜서 맞았습니다. 이후 kwoncycle은 C, 저는 G로 넘어갔습니다. petamingks는 J를 반드시 풀어오겠다며 사투에 들어갔습니다.

 

~0:49

 

G를 봤는데 저번에 코포에서 데인 XOR 해싱을 쓰면 잘 될 것 같았습니다. 이걸 짜느라 3년만에 팀 노트를 처음 볼 수 있었습니다. 처음 써 보는 테크닉이라 걱정이 많았는데 다행히 한 번에 맞을 수 있었습니다. kwoncycle은 C..의 사풀을 완성했고, petamingks는 이 때부터 J와 함께 컴퓨터에 들어갔다 나갔다를 무수히 반복하게 됩니다.

 

~1:42

 

kwoncycle과 petamingks가 각각 C와 J에 매진하는 동안, 저는 스코어보드를 따라가기로 했습니다. 많이 풀린 문제가 대충 B와 H였는데, 일단 B를 먼저 봤습니다. B는 이상하게 쓰여진 코드를 해석해야 하는 문제였습니다. 원래였다면 이런 문제는 CTF를 뛰는 kwoncycle을 주었겠으나, C를 열심히 짜고 있었기에 제가 하기로 했습니다. 다행히 코드가 크게 어렵지는 않아 해석을 빨리 할 수 있었고, 마지막 처리에서 PBDS가 필요해 그것만 신경쓰면 되었습니다. B의 풀이는 AC보다 상당히 빠른 시점에 완성되었고 저는 F 풀이를 정리하고 있었는데, 더 이상 늦어지면 안 될 것 같아 컴퓨터를 뺏고 짜서 맞았습니다.

 

~3:00

 

이후 1시간 넘게 4솔 상태를 유지했습니다. 이 시간 동안 어떤 일이 있었냐면 1) 제가 F를 빠르게 짰지만 의문의 WA를 받았습니다. 2) 머신을 꽤 차지했던 C 풀이가 틀렸음이 밝혀졌습니다. 3) J는 위 두 문제에 치이며 컴퓨터와 종이를 반복하고 있었습니다. 이런 답도 없는 상황이 반복되었고, 저는 F 코드를 정말 열심히 보았으나 틀린 점을 전혀 알 수 없어서 그냥 자리에 앉아 있었습니다. 다행히 J에 컴퓨터를 많이 할당한 결과 예제가 제대로 나오기 시작했고, -파- 당할 가능성이 꽤 커 보였으나 한 번에 맞을 수 있었습니다. 그리고 F의 틀린 부분도 빨리 찾았는데, vector 초기화를 resize로 하려 한 것이 원인이었습니다. 평소에 전혀 하지 않던 실수인데 이걸로 페널티를 꽤 차지했기 때문에 마음이 아팠습니다.

 

~4:32

 

이후 상위권 팀 모두가 푼 H에 세 명 전부가 달라붙었습니다. 다만 다들 상당히 지쳐있어서 맞는 풀이에 도달하기가 쉽지 않았고, 나이브를 짜 돌려보았으나 큰 도움을 얻지는 못했습니다. 이 때의 분위기는 '페널티 생각하지 말고 그냥 각자 맞다 싶으면 짜자' 였습니다. 먼저 petamingks가 사풀을 냈으나 틀렸고, 이후 저와 petamingks가 모두 풀이를 생각해냈지만 달라서 petamingks의 풀이부터 구현했습니다. 제출했으나 다행히 WA가 아닌 TLE를 받았고, -파- 당한 것이라는 강한 확신과 함께 인간 ChatGPT로 빠르게 번역해서 낸 결과 다행히 맞을 수 있었습니다. 이후에는 E 설명을 들었는데, 2년 전 기출과 거의 유사하다는 사실을 원망하며 대회가 끝났습니다.

 

문제별 후기

 

A (?, Not solved) : 문제를 읽지 않았다.

B (P3~4, solved by leo020630) : 코드를 해석하면 대충 어떻게 할지 감이 오는데, 마무리 부분에서 set의 k번째 숫자를 알아야 해 세그 이분탐색이나 pbds를 사용하면 된다. 

C (D?, Not solved) : 복잡한 기하+그리디 문제이다. 그리디한 방법을 떠올려도 증명이 쉽지 않고, 구현도 복잡한 것 같다.

D (S1~2, solved by kwoncycle) : 케웍+주어진 식을 잘 계산하면 되는 것 같다.

E (D2~3, Not solved) : 2년 전 ICPC, SCPC, 서강대 등 정말 많이 나온 문제이다. 문자열이 여러 가지라 아호코라식을 쓰거나 기존 문제처럼 해싱을 잘 하면 될 것 같다.

F (P1, solved  by leo020630) : 제한이 친절하고 DP 식도 쉬운 편이라 최적화를 잘 하면 된다. DnC로 풀었다는 사람들이 많은데, 나는 레이지 스위핑이 먼저 보여 이 방법으로 풀었다.

G (G3~4, solved by leo020630) : TL이 넉넉해 대충 아무 방법으로 풀어도 될 것 같다. 나는 XOR 해싱이 제일 쉬워 보여 바로 뚫을 수 있었다.

H (P2~3, solved by petamingks) : 문제는 간단한데, 마땅한 방법이 잘 떠오르지 않는다. 우선 한 열에서 더 큰 수는 반드시 쓰인다는 점을 관찰해야 하며, 여기서 DP로 발전시키면 된다. 풀이를 들었지만 심신미약 상태였기에 잘 기억이 나지 않는다. 업솔빙 예정

I (S1~2, solved by leo020630) : 앞부터 그리디하게 채워나가면 된다. 구체적인 증명은 모르겠는데, 맞는 방법이라고 강한 확신을 가질 수 있다.

J (P1~2, solved by petamingks) : 복잡한 Digit DP라고 한다. 이런 문제는 한국에 잘 나오지 않는 편이어서 흥미로웠다. petamingks의 코드가 python임에도 불구하고 150줄을 넘어갔던 것 같다. 멋지다.

K (?, Not solved) : 문제를 읽지 않았다.

L (?, Not solved) : 문제를 읽지 않았다.

 

대회 결과

프리즈 이후에는 풍선을 주지 않는 것으로 알고 있었는데, 저희 팀이 받았기 때문에 뭔가 달라졌나 싶어서 H를 푼 이후에 풍선을 열심히 셌습니다. 대충 세 본 결과로는 동상 컷에 아슬아슬하게 걸렸던 것 같은데, 막상 까보니 장려상 1등이라 상당히 아쉬웠습니다. 되돌아보면 운영이 정말 완벽했다고 느낀 작년과는 다르게, 올해는 허술한 점이 많았습니다. 1) C를 잡지 않았거나 2) F에서 이상한 실수를 하지 않았거나 3) 문제 분배를 잘 해 H를 petamingks가 더 일찍 보았다면 등수가 2~3개는 올라갔을 것 같습니다. 다만 최상의 운영이 아니었음에도 결과가 괜찮았다는 것은 나름 긍정적인 부분이라고 생각합니다.

 

올해에는 설카 팀들이 전반적으로 강하고, 숭실대를 비롯해 타 대학에도 강한 팀이 많아 장려상만 타도 잘한 것이라 생각했는데 생각보다 좋은 결과를 얻게 되었습니다. 아마 B나 J등 시간을 많이 잡아먹는 문제가 많아 다들 말렸던 것 같습니다. 대회에서 정말 중요한 것은 그 날 말리지 않고 하던 대로 하는 것이라 생각하는데, 저희 팀이 이 부분에서는 강점을 가지고 있었다고 생각합니다. 아마 큰 문제가 없으면 슈퍼리저널에 가게 될 것 같은데, 언제 올지 모르는 기회이기 때문에 내년에도 공부를 열심히 할 것 같습니다. 

 

후기

작년에는 나름 저와, 팀과, 학교의 긴 무관을 끊어낸 상이었기에 벅차서 후기를 썼는데 올해는 그 정돈 아니고.. 마냥 기분이 좋습니다. 제가 블로그에 특별히 언급하지는 않았지만 포스텍의 PS 동아리인 POSCAT이 이번 년도 들어 나름 많이 활성화 되었는데, 본선에도 3팀이나 오고 2년 연속으로 상도 타니 포스텍이 PS 판에서 자리를 잡아가는 과정인 것 같아 보람을 느끼고 있습니다. 이제 PS 잘하는 신입생만 들어오면 될 것 같습니다. 

 

대회 자체도 기념품이나 일정을 비롯한 여러 측면에서 더 나아진 것 같습니다. 작년에 공지되지 않았던 몇 부분들도 올해는 공지가 잘 되었고, tech talk도 원래 지루해서 잘 듣지 않는데 PS를 굉장히 열심히 하시던 분들의 강연이라 비교적 열심히 들었던 것 같습니다. 무엇보다 슈퍼리저널을 해외에서 해서 기쁩니다.

 

아무래도 ICPC와 롤드컵 기간이 겹치다 보니 언급을 하지 않을 수 없는데, 올해 역시 작년과 마찬가지로 많은 서사가 대회를 빛냈습니다. 작년 후기를 마무리할 때에는 데프트의 중꺾마를 사용했는데, 올해는 다른 인상 깊은 말이 있어 가져와 보았습니다.

 

 

비록 제가 우승을 한 것은 아니지만, 작년의 수상이 운이 아니었음을 증명한 것 같아 뿌듯합니다. 저는 이제 제가 진짜 실력 있는 사람임을 보여주기 위해 더 공부할 계획입니다.

 

특히 팀원들에게 감사한데, 저는 지난 1년 동안 스스로 1옵션이 되어야 한다는 부담감에 싸여 있었으나 팀원들이 잘 해준 덕분에 수상까지 할 수 있었던 것 같습니다. 또한 다른 POSCAT 부원들, 그 외 모든 분들께 감사의 말씀을 전합니다.

 

읽어주셔서 감사합니다.