UCPC 2025 예선

2025년 7월 12일에 UCPC 2025 예선에 참가했습니다. 팀명은 세상에 나쁜 언어는 없다로, 아희한국1등 sciencepark, 엄랭한국1등 gs20036, 알골한국1등 gs22059로 이루어진 팀입니다. 저를 제외한 두 분은 경곽 38기 (23학번) 선배님들이십니다. 예선을 치는 날짜를 기준으로, 백준 솔브수 랭킹을 따졌을 때 세 닉네임은 모두 참입니다. (팀명은 거짓입니다. 알골은 나쁜 언어입니다.)

결과는 9+519/11=#10으로, 널널하게 본선에 진출했습니다.

팀 구성

팀은 3월 8일에 생겼습니다. gs20036님이 ‘팀하실?’을 선언해서 별 생각 없이 알겠다고 했습니다. 지금 생각하면 좋은 선택을 한 것 같습니다.

팀을 일찍 구성한 것치고 예선 전까지 팀연습은 한 번도 해보지 않았습니다. 일단 아무리 박아도 예선을 떨어질 것 같지는 않아서, 예선 세팅의 팀연습을 할 필요를 안 느꼈습니다. 3명의 학교가 모두 다르기도 하고, UCPC 외에 다른 대회를 이 구성으로 나갈 계획이 있지도 않고… 뭐 이런저런 핑계를 댈 수 있겠지만 결론적으로 예선을 잘 쳤으므로 굳이 핑계를 더 대지는 않겠습니다.

팀명을 고를 시기가 되었고, 두 팀원은 각각 BOJ 언어 랭킹에서 각각 아희 1등과 엄준식 1등을 가지고 있었습니다. 경곽 38기에는 난해한 프로그래밍 언어 동아리가 있었지만 40기까지 내려오지 못했습니다. 그래서 저는 임의의 요상한 언어의 랭킹에 들어가 있지는 않았습니다. 풀린 문제수가 적은 언어를 찾아봤더니 Algol 68의 1등이 단 6솔브였고, 빠르게 1등을 먹어서 팀명을 완성했습니다. 이 글을 올리고 나면 쉽게 1등을 뻇기려나 싶습니다만, 저는 굳이 다시 알골을 만지고 싶지는 않네요. (help.acmicpc.net의 예시 코드를 보면, A+B를 푸는 데 조건문을 쓰는 걸 볼 수 있습니다. 너무재밌어보이지않나요???)

예선은 대전에서 치기로 했습니다. 런 동방에 간지 꽤나 오래되었어서 (봄 대회 때 못 들렀으니 적어도 반년이 넘었지요) 카이스트에 놀러가는 셈치고 다녀왔습니다. 다만 생각보다 기차표를 구하기 어려웠습니다. 버스를 타려다가 대회 전날에 운 좋게 서울역에서 대전까지 52분 만에 닿는 표를 구했습니다.

대회 당일

집에서 대전역까지는 2시간 4분이 걸렸습니다. 서울역에서 가만히 서서 20분 정도를 버린 것을 생각하면, 카이스트가 정말로 국제캠퍼스랑 비슷한 거리에 있다는 것을 느낍니다. (물론 교통비가 5배 정도 들긴 하지만요.)

대전에서 카이스트까지 처음으로 지하철을 이용해봤습니다. 그래서 대전지하철은 처음 타봤는데, 각종 표지판이나 안내가 오래된 것 같다는 감상 외에는 서울의 그것과 크게 다르지 않았습니다.

그렇게 카이스트 기숙사이자 오늘의 회장인 희망관에 도착했습니다. 개인적인 감상으로는 예전에 여러 번 묵었던 사랑관에 비해 건물이 꽤나 좋아 보였습니다. 1인실이고 신기(?)하게도 개인 냉장고가 있더군요.

누군가가 SCPC 예선에서 맞왜틀을 박으며 디버깅하는 걸 잠깐 기다리다가 어은동에서 점심을 먹고 (한, 중, 일, 양 중에서 랜덤을 돌렸고 양식이 나와서 스파게티를 먹었습니다) 희망관의 공용 휴게실 같은 곳에 자리를 잡았습니다. 코드가 책상으로부터 멀리 떨어져 있다는 점을 제외하고는 꽤나 좋아 보이는 공간이었습니다.

‘예전에는 쉬운 문제 빨리 풀기 원툴이었던’ gs20036님, 명목상 레이팅이 가장 높(고 아마도 실력도 가장 높을 것 같)은 sciencepark님, 그리고 저 순으로 ABCD, EFGH, IJK(L)을 잡기로 했습니다.

대충 세팅을 해 두니 1시 10분 정도였습니다. 그때쯤 깨달은 것이, 하나는 이 공용 휴게실이라는 곳에는 에어컨 리모컨이 없다는 점, 또 하나는 생각보다 방이 많이 덥다는 점이었습니다. 약간 자리를 잘못 잡은 것 같다는 후회와 함께 시간을 때웠습니다. 예전에 sciencepark님이 만드셨다는, 매우 고퀄리티로 보이는 어떠한 변형 체스 게임을 했습니다. 생각보다 재밌었습니다.

체스에서 두 번 지고 나니까 55분이 되었습니다. 슬슬 준비를 했습니다. 그러면 안 될 것 같은데, 긴장이 하나도 안 됐습니다.

극초반 (~10분)

• gs20036님이 A(검수 B5)를 보고 50초에 구현해서 맞았습니다. 퍼솔보다 0분 늦었습니다.
• 바로 B(검수 S1)로 넘어가서 4분에 AC가 나왔습니다. 퍼솔보다 2분 늦었습니다.
• sciencepark님이 E(검수 G1)가 어떤 대회에 나온 문제와 비슷하다고 하며 구현해서 6분에 맞았습니다. 퍼솔보다 1분 늦었습니다.
• 저는 I(검수 G4)를 봤습니다.
• 최대는 그냥 블럭들을 x로 떨어뜨리면 되고, 최소는 최대한 붙여놓은 뒤에 유파를 돌리면 되는 문제였습니다.
• 바로 구현해서 10분에 맞았습니다. 퍼솔보다 3분 늦었습니다.
• gs20036님이 리모컨 없이도 에어컨을 켤 수 있다는 사실을 관찰해서, 이내 방이 시원해졌습니다.

이 시점에 전체 2등이었던 것으로 기억합니다.

초반 (~30분)

• J를 읽었습니다. 뭔가 컨스트럭션을 하면 간단하고 예쁜 그래프가 나올 것 같았습니다.
• D와 H의 퍼솔이 나온 것을 보고했습니다.
• K를 읽었습니다. 나코더 24반년 4번 트리DP(P4)의 상향일 것이라 생각했고, 잠깐 잡아봤습니다.
• K가 24반년4에 비하면 극극극상향 문제라는 것을 깨달았습니다.
• J의 케이스 몇 개를 그려봤습니다. 뭔가 보이지 않았습니다.
• FGH를 읽은 sciencepark님은
  • G가 deque dp 같다
  • FGH 중에 잡을 만한 문제가 없다
• 고 하셨다가 이내 H가 풀린다며 구현하러 가셨습니다.
• CD를 읽은 gs20036님은 D가 풀린 것을 보고 D가 풀만하다면서 가셨습니다.
• G와 C의 퍼솔이 나온 것을 보고했습니다. 잠깐 G를 읽어보았고 다시 J로 돌아갔습니다.
• H(검수 P4)와 D(검수 G3)가 30분에 동시에 풀렸습니다.

이 시점에도 전체 2등이었던 것으로 기억합니다.

중반 (~90분)

• C와 J의 퍼솔이 나온 것을 보고했습니다. J를 더 오래 잡고 있는 것은 의미가 없을 것 같아서 sciencepark님께 넘기고, 저는 C를 보러 갔습니다. 이전에 G가 풀렸기 때문에 gs20036님은 G를 보러 가셨습니다. 즉 문제를 한 바퀴 돌렸습니다.
• C(검수 D5)는 구간이 나오는 문제였습니다. 일반적인 구간 문제와 다르게, C번은 구간의 시점과 종점의 중점을 기준으로 정렬하고 그리디하는 것이 최적인 문제라는 것을 관찰했습니다.
• 얼마 안 가 sciencepark님이
  • J(검수 P4)가 내가 잡아야 되는 문제처럼 생겼다
• 고 하여 계속 J를 잡으셨습니다. 조금 지나 제가
  • C가 내가 잡아야 하는 문제처럼 생겼다
• 고 하여 저도 C를 더 잡기로 합니다.
• C에서 어려운 것은, 레이저 질의가 주어질 때마다 각 구간이 어디로 가는지는 구간 중점에 대한 정렬을 기준으로 하지만 얼마나 이동하는 지는 구간의 종점 (왼쪽으로 이동하는 구간) 혹은 시점 (오른쪽으로 이동하는 구간)을 기준으로 하기 때문에 그리디로 때우기가 매우 어렵다 - 아마도 불가능하다는 점임을 관찰했습니다.
• gs20036님은
  • G는 내가 잡으면 안 될 것처럼 생겼다 / $N^4$는 알겠는데 $N^3$은 모르겠다
• 등의 말을 하셨지만, sciencepark님과 제가 각각 J와 C에 침을 발라둔 관계로 나머지 문제들을 읽으셨습니다.
• sciencepark님이 J의 풀이를 내셨고 구현해 맞았습니다. 75분쨰였습니다.
• gs20036님은 F(검수 D5)가 다이나믹 세그와 함께라면 해결할 수 있을 것 같다는 말을 하셨고, 궁극의 웰노운 알고리즘을 올리는 모 블로그의 구현체를 돚거해다가 구현을 시작하셨습니다.
• 저는 C에서 위의 ‘그리디’를 그리디 말고 합 세그나 펜윅으로 구현할 수 있다는 사실을 알아냈습니다. 그리고 풀이가 완전히 구체화되지는 않은 상태로 구현을 시작했습니다.
• sciencepark님이 G로 되돌아가셨습니다.

후반 (~150분)

• sciencepark님이 사실 G(검수 P3)가 쉽다고 하시며 G를 짜러 가셨습니다.
• gs20036님이 F(검수 D5)의 솔루션을 제출했으나 MLE를 받았습니다.
• sciencepark님이 G의 솔루션을 제출했으나 WA를 받았습니다.
• 저는 C(검수 D5)의 구현을 만들었고, 예제가 돌아가는 것을 확인하여 제출했지만 RE를 받았습니다.
• sciencepark님이 G의 솔루션을 수정해 제출하셨고 AC를 받았습니다. 이 시점에 한 자리 후반대 등수였던 것으로 기억합니다.
• gs20036님이 사실 F의 솔루션의 시복이 너무 크다고 하시며 풀이를 엎었습니다.
• 저는 C에서 랜덤한 케이스를 생성하는 코드를 짰고 RE가 나오는 부분을 찾아 수정 제출했고, WA를 받았습니다.
• 스코어보드가 프리즈되었습니다.
• sciencepark님이 제 C 풀이를 들으셨고 아마 맞는 풀이라 생각하셨습니다.
• gs20036님과 sciencepark님이 F를 잡으셨던 것 같습니다.
• 저는 C에서 랜덤한 케이스를 더 많이 생성해 보았고 비용이 음수가 나오는 경우가 있는 것을 확인했습니다.
• 저는 그러한 작은 케이스를 하나 만들어 구현의 모든 수식을 손으로 적어서 디버깅했습니다.
• 저는 식에 오류가 있다는 사실을 확인했습니다.

극후반 (~180분)

• 저는 C번에서 식의 오류를 수정했고, 다시 예제가 나오며 음수가 나오지 않는 것을 보고 제출했지만 WA를 받았습니다.
• 저는 펜윅에서 구간 범위를 잡는 과정에 어떠한 오류가 있을 것이라 예상했으나, 어떤 오류가 있는지는 생각해내지 못했습니다.
• 저는 대회가 15분 남은 관계로 이제 패널티에 상관 없이 어떻게든 제출해 봐야겠다고 생각했습니다.
• 저는 펜윅에서 구간 범위에 오류가 있는 경우 이를 수정할 수도 있는 픽스를 적용해 제출했고 AC를 받았습니다.
• gs20036님이 패널티를 계산해 프리즈 이전 9문제를 푼 팀 중 이길 수 있는 팀이 있는지 확인해 보았고, 어림도 없다는 점에서 프리즈 이전보다 등수가 떨어질 것이라 확신했습니다.
• 슥보의 팀 이름을 구경하고 관심법을 이용해 팀의 인원을 찍어 봤습니다. RGB_ICPC의 Bark Jongkyung 이라는 이름이 재밌었습니다.

이후

• 오픈 대회가 늦는 관계로 대부분의 다른 팀 참가자 분들과 소통 - 특히 풀이 얘기 - 을 많이 못 했습니다. 런 수뇌부를 중심으로 한 카르텔의 몇 팀, 엔드게임과 포킹을 중심으로 한 카르텔의 몇 팀, 마작과 해병대와 마술 쇼를 좋아하는 사람들이 많은 어떠한 카르텔, 경곽 40기가 소속된 몇 팀과 대화를 나눴습니다.
• 런 동방에서 쌀먹을 하고 집에 돌아왔습니다.
• 슥보가 공개되었습니다. 최종적으로 10등을 한 것을 확인했습니다. 대체로 만족스러웠습니다.

리뷰

• 처음에 잡은 세 문제 중, I는 바로 풀어야 하는 문제였고 빠르게 풀어서 잘했다고 생각합니다. J와 K는 (솔브수로 미루어보면) 어려운 문제였고, 그래서 초반에 문제를 많이 못 풀어서 버스를 탔습니다.
  • sciencepark님이 J를 관찰하시는 속도를 보고 넘기길 잘했다고 생각했습니다.
• 그런데 I를 제외하면 저는 C밖에 풀지 못했고, 저는 C를 푸는 데 적어도 2시간을 사용했습니다. 풀이를 내는데 30분이 넘게 걸린 것은 괜찮다 생각하지만(저는 C가 P2..D5라 생각하는데, 그러한 문제를 실전에서 1시간보다 빨리 발상했으면 빨리 생각해낸 편입니다), 구현과 디버깅에 1시간이 넘게 걸린 것은 아쉽습니다. 특히 저는 아직도 왜 제 픽스가 문제를 해결했는지 알지 못합니다.
• 다만, C를 아무리 빠르게 짰어도 지금 시점에서 패널티를 90분이나 줄이는 것은 어려워 보입니다. 따라서 등수는 아마도 나올 수 있는 최적의 등수에 가깝게 나오지 않았나 싶습니다.
• 한 가지 아쉬운 건 F인데, 저는 C에 너무 오래 있었으므로 F를 볼 시간이 없었던 건 자명한 듯합니다. C를 좀 빠르게 - 프리즈 전에 - 잡았다면 뭐라도 생각해볼 수 있지 않았을까 싶어 좀 아쉽습니다.
• 이번 대회에서 팀으로서의 역량을 내지는 않았습니다. 그냥 개인의 능력으로도 9솔이 어?렵?지 않?게 가능했습니다. 뭐, 제가 C의 풀이만 내고 다른 분에게 구현을 던진 후 F를 봤다던가 해도 솔직히 F가 풀렸을 것 같지는 않습니다. 그리고 대회 중반 이후에는 무슨 짓을 해도 본선에는 가겠다는 생각이었어서, 후반에는 대회 시작 전보다도 긴장을 안 하고 문제를 풀었습니다. (다만 저는 어떻게든 C는 풀겠다는 생각이 있긴 했습니다.)
• 초반 푸쉬가 굉장히 잘 되었습니다. A는 브론즈이므로 예외라 생각하고, 각 인원이 처음 읽었던 B/E/I가 모두 적당한 스탠다드한 골드 이하의 무언가였다는 점이 크게 작용했습니다. 다음에 D와 H가 빨리 풀린 것도 맞고요. (두 팀원분들 모두 초반에 강하신 것 같습니다)
• 또 그래서 그에 비해 후반에 F를 못 풀었다는 점이 아쉽네요.

본선에서 뵙겠습니다. 감사합니다.