2025 서울대학교 SCSC 프로그래밍 경시대회 Div.2 2위 후기

Div.2에서 2등 했다. Div.2에서 2등 했다. 콩콩. 콩콩.

이런 인생 고점의 결과가 나오고 나서 말하면 조금 이상하게 들리겠다만, 순위상을 기대하고 참가한 것은 아니었다. 그냥 아는 얼굴 한 번 보러 마실 겸 나들이 겸 해서 출전한 것 뿐. Div.2는 10등까지 삼성에서 후원한 이런저런 전자기기를 받는데, 지난 대회에서는 Div.2에 참가한 95명 중 37등이라는 애매한 등수를 받았기 때문이다. 그 때 이후로 체급이 딱히 올랐다는 생각은 정말로 한 적이 없는데, 이런 결과를 맞고 보니 체급이란 게 조금은 오른 걸까 하는 생각이 든다. 이젠 정말로 자신에 대한 저평가는 그만해야지. 몰매라도 맞을 것 같다.

생각해 보면 참가신청 때부터 Div.3을 고려하고 있었는데, 그것마저도 자기 자신에 대한 엄청난 저평가였나 싶다.

2회차 새내기

'25학번 2회차 새내기'라는, 재미도 감동도 없는 핸들로 참가했다. 핸들 글자수가 50자 제한이라는 걸 안 알려줘서 길게 하면 짤릴 것 같았고, nflight11 대신 나 자신을 간단하고 명확하게 소개할 수 있는 단어를 찾자니 저 정도밖에 생각나는 것이 없었다. 길게 되는 줄 알았다면 뻘소리로 채웠을 텐데.

뭐 대충 이런 거

0. 입장 전

무슨 일이 있어도 나는 정시에 도착하지 않는다. 20분 이상 빠르거나 20분 정도 지각하거나 항상 둘 중 하나다. 그리고 이런 날이라면 반드시 20분 이상 빨라진다. 서울대 정문에 도착하는 시간을 12시 30분으로 잡고 출발했는데, 또 무슨 조화인지 시공간왜곡이 발생해서 12시 딱 해서 서울대에서 가장 가까운 지하철역인 관악산역에 도착해 버리고 말았다. 그런데 이렇게 일찍 도착한 사람은 나만 있는 게 아니었고...

갑자기 훅 더워진 날씨에 정문 바로 앞에 있는 세븐일레븐에서 차게 식힌 녹차 마시며 쉬고 있었는데, 디스코드에 terrasphere(a.k.a. lulusphere)가 신상이 특정될 수 있는 정보를 남긴 채 막 도착했다는 메세지를 남겼다. 현장에 빠삭한 서울대생이 지나가는데 이 기회를 틈타 꼽사리껴서 안내받으려고 접근했다. 좌반신만 찍어놓고 근처에 있다며 terrahemisphere 드립을 쳤는데 이것도 지금 와서 생각해보니 개노잼이었다.

하지만 서울대생이라고 해서 서울대 전역에 빠삭한 건 또 아니었고, 그래서 사람들이 모여 있다던 버거운 버거(어제까지 문제인 줄로만 알았지, 실존하는 체인점이라고 생각해 본 적은 단 1초도 없었던) 지점까지 갈 때는 지도 어플을 켤 수밖에 없었다. 도착해 보니 익숙한 얼굴이 좀 보였다. 지난 SCSC 프로그래밍 경시대회에서 만났던 toycartoon, StarBlitz, 그리고 Morgorithm의 기둥이 될 gs22059를 포함해서 10명 가까이 모여 있었다. 너무 더워서 아메리카노 하나를 시켰는데, terrasphere가 시킨 버거보다 늦게 나왔다. 이 가게의 프로세스는 스택 기반인가...

조금 늦게 도착한 ychangseok까지 모여서 대인원으로 대회장인 28동에 도착했고, 등록을 마쳤다. Morgorithm 소속인 tjrn3712, pggggggggh이랑 코드포스 레이팅이 높아서 Div.1로 납치되어버린 oh040411과 간단히 인사 나누고 갤럭시 AI 클래스에서 AI 타로를 봐준다길래 그 쪽으로 향했다. 역방향 컵 4가 나왔고, 정신적인 타격을 입는다 뭐 그런 대회운이 나왔다. 완전히 망해버리겠군... 하는 불길한 예감과 함께 간식꾸러미 까먹으며 대회 시작을 기다렸다.

1. 대회

나는 거의 대부분의 대회에서 초반에 빠르게 치고 올라가서 페널티가 낮은 상태로 버텨가며 순위를 사수하는 식으로 임한다. 그래서 그 반대급부로 초반에 말려버리면 머리가 완전히 비어버리는 대참사가 발생한다. 그리고 이 대회에서도 초반 한 시간동안 거의 아무것도 하지 못하면서 머리가 비어버릴 뻔 했는데......

0:03 A WA

0:14 A WA

첫 두 항만 보고 대충 찍어 맞추려고 해서 한 번 틀렸고, 조금 생각을 더 해 보고 \(N=1\)일 때 항까지 생각한 뒤 규칙을 찾으려 했다. 그런데 초항의 계산을 잘못해서 한 번 더 틀리고... 머리가 비어버린 상대로 어떻게든 해 보려고 무슨 짓을 했냐면...

0:15 A AC (+2)

\(N=0, 1\)일 때의 값을 각각 \(0, 35\)라고 추정한 다음, 네 점이 있고 답이 3차 이하의 다항식일 형태라고 믿으면서 손으로 라그랑주 보간법을 돌렸다. 대체 이게 무슨 말도 안 되는 방법인가 싶을 텐데, 절절히 동감한다. 나도 보간법 돌리면서 이것보다 더 확실하고 간단한 실버 레벨의 풀이법이 있을 것이라는 생각을 안 한 건 아니다. 그냥 빨리 한 문제라도 맞히고 싶어서 알면서도 극약처방을 사용한 것 뿐이다.

이 뒤로는 두 번째로 쉬운 문제인 B를 보려다가 또 말려버려서 다음으로 많이 풀린 문제를 보러 갔다.

0:49 I AC (+0)

\(N=de\)이며 \(d\le e\)이면, 리프 노드 수 \(d\)와 리프 노드가 아닌 노드의 수가 \(e\)개인 트리를 언제나 만들 수 있다. 그러니 \(d\)를 최대화한 다음 적당한 트리를 구성하면 된다. 에디토리얼에 있는 예쁜 방법이 있고, 내가 한 것처럼 큐를 쓰면서 구성해 가는 방법이 있다. 이 방법의 구현이 또 생각만큼 잘 되지 않아서 시간을 낭비했다. 하위권까지 떨어졌다가 이 문제를 풀면서 30등대로 올라왔다.

0:53 B WA

1:09 B AC (+1)

그 뒤로 다시 B를 보러 갔다. 문제를 보고 가장 먼저 할 법한 생각은 스택이었고, 스택을 풀이라고 생각하느라 문제를 잘못 읽어버리고, 부분수열을 연속한 부분 문자들로 이루어진 문자열로 착각해버리면서 운영진에게 의미없는 질문을 던져버리기까지 했다. 이 정도면 말려도 정말 대단히 말린 건데... I를 맞히고 돌아오니 답이 보였다. 왼쪽/오른쪽으로부터 \(N\)번째 위치인 O의 왼쪽/오른쪽에는 최소 \(N\)개의 H가 존재해야 한다. 이걸 왜 못 찾고 있었을까 하면서 코드를 짰는데 틀렸다. HHHHOHHHH와 같은 케이스를 생각 안 했다는 걸 깨닫는데 15분 정도가 걸렸다. :blobfacepalm:

여기까지 보고 나니 그 다음으로 많이 풀린 문제들이 F, G 정도였다. G는 누가 봐도 극한의 애드혹이었고 몇 분을 봐도 제대로 된 생각이 들지는 않았다. 다른 문제들을 훑어보고 보니 이게 가장 할 법 하겠다 싶어서 E부터 잡기 시작했다.

1:30 E WA

1:34 E WA

1:35 E AC (+2) / First Solve

\(S\ne C\)인 경우는 굉장히 쉽다. 그래서 \(S=C\)인 경우를 체크해보려 했다. 가장 먼저 생각나는 것은 dp였는데, 생각해 보니 길이가 4부터 14 정도일 때 경우의 수는 브루트포싱으로 쉽게 구할 수 있다. 그 결과를 통해서 선형 점화식을 찾거나 하려고 했는데, 그 전에 보험용으로 OEIS에 집어넣어 보기로 했다. 그런데 이게 되더라. 헐? 물론 경우의 수 그 자체를 뱉는 것이 아니라, 경우의 수 계차수열을 얻었던 것이긴 하다. 그런데 그 계차수열의 선형 점화식까지 주어져 있었고 그러면 쉽게 더 길이가 긴 경우로 확장할 수 있어서 운이 좋았다.

이게 무슨 조화인가 싶어서 얼른 DB를 박았는데, 길이의 최대치를 착각했다. 36 정도면 충분할 것이라 생각했는데 사실 40까지는 가야 했었다. 그걸 눈치채지 못해서 답을 다 얻어놓고도 두 번 틀려서 페널티로 40분을 적립하고야 말았다.

1:51 F WA

2:17 F AC (+1)

처음에는 불안정 정렬의 유무로 답이 갈릴 거라고 생각했다. 그러다가 깔끔히 한 번 틀렸고... 그 뒤에 다시 한 번 생각해 보니 마지막 불안정 정렬 이후의 안정 정렬을 전부 체크해야 한다는 것을 깨달았다. 그래서 그 모든 체크할 만한 것을 tuple에 때려박고 해싱을 하려고 했는데, 실수로 해싱하는 것 자체를 잊어먹고 map에 집어넣어 버렸다. 그 실수를 깨달은 것은 이미 AC를 받고 난 뒤였고...

2:34 J AC (+)

이 문제가 생각보다 많이 풀렸길래 잡으러 갔다. 이것마저 잡아 버리면 다섯 손가락 안에 들어간다는 생각을 하면서 생각을 이리저리 전개해 봤다. 어떤 문자열의, 특정 위치를 중심으로 하는 가장 긴 팰린드롬 길이 판별은 선형에 가능했고, 그 길이가 \(l\)이라면 \(l, l-2, ...\)의 길이를 가진 팰린드롬도 전부 팰린드롬이므로 팰린드롬 부분 문자열의 갯수 판별마저도 선형에 가능했다. 그렇다면 선형 개의 문자열에 죄다 매내처를 때려박으면?의 생각으로 코드를 짰더니 여유있게 돌아갔다.

이 시점에서 2등으로 올라갔다. 1등은 C, G를 풀고 E를 풀지 못한 7솔이었고, 초반부터 빠르게 치고 올라가 버린 탓에 페널티 차이도 대략 4시간이 났다. 우승을 노리려면 2문제를 더 풀어야 해서 그건 깔끔하게 포기했고, 이 뒤로는 D를 살펴봤다. G는 봐도봐도 답이 안 보이고, C나 H는 편린마저도 감이 잡히지 않아서. XOR weighed set covering 문제라면 논문 레벨인 것 같아서 논문을 뒤져보면서 90분을 보냈다. 프리즈 이후로 5솔 중 페널티가 괜찮은 사람들이나 6솔 경쟁자들이 문제를 더 풀어서 2등 자리를 뺏기지는 않을까 조마조마했는데 그런 일은 벌어지지 않았고 무사히 2등 자리를 지켰다.

2. 종료 후 (TBU)