제4회 고려대학교 MatKor Cup : 2024 Winter/Spring 3등 후기

간지나는 포스터와 멍충미 넘치는 호랑이... 고양이?

온사이트 대회는 희귀하다. 특히 자대생만을 대상으로 하지 않는 온사이트 대회는 정말로 희귀하다. 아직 신학기라 바쁘지 않을 시점에 열리는 온사이트 대회라면, 그렇기 때문에 참가하지 않을 이유가 없다. 심지어 참가비까지 없는데?

ICPC 2023에서 같은 팀이었던 now_cow가 검수진으로 있다며 홍보를 했다. 포스터를 보자마자 바로 참가신청을 날렸다. 예비소집 전날 낮까지 연락이 없어서 똑 떨어진 줄 알았지만 다행히 참가인원이 수용력을 초과하지는 않은 모양인지 온사이트 참가대상이 되었다.

개인대회이고, 어느 정도는 내 영역에 있는 수학 테마의 문제가 나오는 데다가 대회 자체가 매콤하다. 풀 수 있는 문제는 다 풀고 긁을 수 있는 것도 다 긁자는 마음가짐으로 대회에 임했다. Python으로 인한 시간초과에 발목을 잡히지 않기를 바라며... 대회 목표는 예비소집 / 본선 각각 1퍼솔 이상. 그리고 수상권에 들면 좋겠다는 마음가짐. 몇 명이 수상 대상인지는 모르겠으나.

 

예비소집:

　프리즈 시점 4위 (470/600, 203분)

　전체 5위 (470/600, 203분)

무료로 개인정보를 가려드립니다. Frozen :: Live

할 수 있는 한계까지 했다고 생각한다. 4문제 중 3문제를 풀었고, C번은 아무리 생각해도 풀이가 생각 날 것 같지가 않아서 일단 긁을 수 있는 건 어느 정도 긁었다. 50점이냐 55점이냐 둘 중 하나였어서 그냥 비효율적인 코드로 시간초과 받고 50점만 받아갔다.

생각보다 많은 사람이 안 왔다. 전체 62명 중 와서 1제출이라도 한 사람은 20명밖에 안 된다. 상당한 고수들이 안 온 사람 중에 있어서, 62명 전원이 대회를 치뤘다면 10등도 건지기 힘들었을 것이다. 아마도? 그래도 목표였던 1퍼솔은 가져갔다는 데 의의를 두고 있다.

0:09 PA 100/100 (+1)

간단한 수학 문제. 종이에 식을 차분히 적어 보면 답이 보인다. 걸러내야 할 케이스를 걸러내지 못해서 5분을 허비했다. 페널티 20분은 추가고. -2를 출력할 일은 없는데 도대체 왜 -2를 넣어 놨을까.

0:21 PD 200/200 (+1)

B랑 C에 비해 D가 식이나 지문압박은 조금 있지만 그럼에도 불구하고 풀이가 바로 보이는 문제였다. 적어도 나한테는. 그래서 그 문제부터 손을 대기 시작했다.

\[f(a)=\left|\sum_1^N(y_i-ax_i-b)^3\right|\]

위 식을 최소화하는 \(a\)를 \(\mathcal O(N)\)에 찾는 문제이고, 이는 \(\Sigma\) 내의 식을 전개한 다음 \(a\)에 대한 함수로 보고 삼분탐색을 돌리면 쉽게 풀 수 있다. 온사이트에서는 나 포함해서 프리즈 전까지 위 사진에 보이는 네 명만 정답을 맞혔고, 같은 시간에 열린 오픈 컨테스트에서도 정답자가 세 명밖에 없었다. 그렇게 어려운 문제는 아니라고 느꼈는데, 까 보니 이런 결과라 기여창이 기대가 안 될 수가 없다.

디버깅용 출력을 제거하지 않고 그대로 제출해서 한 번 틀렸다. 등신......

0:44 PB 120/120

모양을 보고 뇌 정지 한 번, 그리고 자가 균형 이진 탐색 트리의 일종이라고 하는 AVL 트리라는 신개념에 뇌 정지 한 번. 정신을 차리고 보면 간단한 DP로 풀 수 있는 문제였다. 대칭되는 몇 가지 케이스를 쳐낼 수 있어 보였지만 그냥 무식하게 7가지 모든 \(S\)에 대해서 DP를 다 돌리고 쿼리가 들어 올 때마다 처리해 주는 것으로 방법을 정했다. 뇌보다 손을 더 많이 쓴 케이스가 아닐까. ㅋㅋ.

1:06 PC 50/180 (+1)

아무리 봐도 \(\mathcal O(N^2)\)만 떠오르고 \(\mathcal O(N\log N)\)이나 그보다 개선된 시간복잡도 풀이가 생각이 나지 않았다. 5점 조건만 없었으면 가능했는데 5점 조건을 어떻게 빠른 시간 안에 처리할 수 있는지는 감도 안 잡혀서...

추월당하는 것만 막고자 비효율적인 코드로 50점을 챙기고 조기종료했다. 프리즈가 풀려 봤자 스코어보드 모양을 보면 한 명에게만 추월을 허용할 것 같다.

 

본 대회:

　프리즈 시점 2위 (1567/5000, 1044분)

　전체 3위 (1624/5000, 1584분)

Frozen

Live

이렇게 잘 칠 줄 몰랐는데, 퍼포먼스가 예상을 아득히 초월해서 나왔다. 신이 들렸다까지는 아닌데, 아는 범위에서 문제 나왔다 정도? 그리고 온전히 풀어낼 수 없을 것이라고 판단한 이후 후반 문제를 잘 긁은 것이 주효했다. 온사이트에서는 동상을 받았고, 내로라하는 고수들이 참여 가능한 오픈 콘테스트와 합쳐 봐도 10등 안에 든다.

실력이 부족해서 입상과는 영 연이 없는데, 프리즈 스코어보드에서 내 밑에 있는 사람이 역전을 보여주더라도 5등은 지킬 것 같다. 왜 같다냐고? 대회 종료 30분 남겨 두고 이 후기를 쓰고 있기 때문이다. 할 수 있는 걸 다 해서 더 이상 생각나는 것도 없고, 제출해 봤자 몇 점 긁지도 못할 것 같아서 해야 할 후기부터 미리 쓰고 있다.

UPD) 결국 온사이트에서 3등을 지켜내며 3등상을 받았다. 준우승 자리를 지켜내고 싶었는데 D와 I를 풀어내지 못하면서 2등인 Serendipity__와 격차가 한참 벌어지고 말았다. 내로라하는 고수들이 참여 가능한 오픈 콘테스트와 합산해 봐도 전체 6등이다! 무려 xiaowuc1와 비슷한 결과라니...

0:04 B 100/100 (+1)

A보다 B를 먼저 봤다. 목표가 퍼솔이라 빠르게 풀어낼 수 있는 B 먼저 보고 A로 돌아가도 페널티에 큰 영향 없으리라고 생각했기 때문이다. \(a>b\)를 생각 안 해 줘서 한 번 틀렸지만 금방 수습했다. 수습해도 제일 빠르더라.

0:06 A 100/100 (+1)

이것도 생각을 잘못해서 한 번 틀렸다. A 치고 고려해야 할 게 많아서 뇌 빼 놓은 코딩으로는 아차 하면 틀릴 것 같은 문제다. MatKor의 매운맛은 익히 들었지만 첫 문제부터 답지 않은 매콤함이 들어 올 줄은... 이걸 푼 시점에서 내가 1등이 됐다.

0:08 G 250/250

PD와 지수가 3인지 4인지만 차이가 있는 문제. 번개같이 코드를 복사하고 식만 살짝 고쳤다. 고려해 볼 것도 없이 바로 AC. 스코어보드에 독을 풀어넣는다는 전략이 통했을지는 모르겠다. G를 풀어 낸 사람이 생각보다 적은 걸 보면 그냥 스코어보드를 안 보고 자기 페이스대로 임한 사람이 많은 것 같은데... 조금 아쉽다.

0:20 E 180/180

C랑 D를 봤는데 이게 뭐야 싶었다. D는 아예 감이 안 오고 C는 구현이 좀 뇌 빠질 것 같아서 다음 문제 E로 갔다. 조합론 스멜이 강하게 나서 얼른 잡아먹었다. 세 번째 퍼솔 획득이었다.

1:06 H 300/300 (+1)

라그랑주 승수법을 내가 PS에서 쓸 거란 상상은 못 했다. 변분법 쓰는 문제도 있는데 이런 문제가 없으리란 보장은 없지만. 식 정리를 한참 했는데, 어처구니없게도 시간초과가 decimal 모듈 사용에서 났다. 실수오차를 배제하려고 그랬는데 오히려 페널티만 적립하게 되었고, 2분 차이로 퍼솔을 놓친 건 아쉽기 그지없다.

이 시점에서 2위로 떨어졌고, 프리즈 끝날 때까지 1등과 2등은 바뀌지 못했다. 1등의 퍼포먼스가 워낙 압도적이었어서 어쩔 수 없긴 하다. 자연재해 만난 셈 쳐야지.

1:47 C 100/100

어차피 1등은 기대하지도 않았다. 이제 보자마자 답이 생각나는 문제는 전부 다 먹어치운 터라 구현이 지나쳐서 거른 문제들을 풀 타이밍이었다. 삑사리가 너무 나서 시간을 허비했지만, 틀리지 않고 한 번에 맞춘 것만 해도 이득이라고 생각한다.

2:18 N 224/500 (+1)

확실하지 않은 120점짜리 D를 푸느냐, 아니면 뒷번호 문제들에서 서브태스크를 긁어서 점수를 많이 따 가느냐. 후자를 택했다. C의 엄청 매워진 버전이었는데, 고려해야 할 케이스를 세 가지로 압축시키면 200점 넘게 긁을 수 있었다. 식 정리 후 삼분탐색을 갈겼고, 필요한 만큼 점수를 받았다.

UPD) 굴절률로 생각해서 스넬의 법칙처럼 경로를 잡고, shooting으로 구해도 문제가 없다고 한다. 세상에... 이런 생각을 어떻게 했는지. 그리고 문제로 어떻게 만들었는지가 감히 상상도 가지 않고, 좀 무섭다.

2:41 M 137/450

이것도 가우스 소거법을 이용한 키르히호프 정리를 통한 스패닝 트리의 계산이 가능했던 서브태스크만 긁었다. 서브태스크라고 해도 플래티넘 수준인 것 같은데, 그러면 전체 문제는 높은 확률로 다이아라는 소리다. 유서깊은 매운맛 MatKor...

3:15 L 128/400 (+1)

어떠한 다항식의 K차항 계수를 구하는 문제. 라는 것도 파악했고 FFT까지 들고 왔으나 목표했던 서브태스크는 긁지 못했다. 210점을 노리고 열심히 공략했는데, 대체 어디서 시간초과가 난 건지 모르겠다. 이게 DP라면 진짜 슬플 것 같은데...

UPD) DP더라. 젠장......

3:19 K 48/400

자명해 보이는 케이스만 먹기로 했다. 자명하지 않은 케이스는 대체 어떻게 풀어야 할지도 감이 안 잡히는 바람에...

4:20 D 32/100

대체 무슨 방법으로 풀어야 할지도 모르겠다. 가장 가까운 두 점 풀이인가? 머리가 아프다... 일단 절대 D에 있어서는 안 되는 건 확실하다. 이래놓고 쉬운 알고리즘으로 쉽게 풀면 환장할 노릇이겠지만, 그럴 것 같지는 또 않다.

4:40 P 25/600

가장 어려운 문제지만, 가장 쉬운 서브태스크는 생각 없이 백트래킹으로도 풀리는 문제다. 무지성 백트래킹을 갈겨서 마지막으로 점수를 얻어냈다.

 

대체로 내 영역에 있는 문제라서 즐거웠는데, 같이 대회 치뤘던 Serendipity__는 자기 영역이 아니라서 헤맸다고 한다. 이런 문제가 대회 당 하나 혹은 둘 있어도 충분한 것들이긴 해서, 영역이 PS보다는 수학에 치중되어 있는 셋이긴 하다. 그래도 이런 대회가 하나 정도는 있어야 할 것 같다는 생각은 든다. 절대 내가 잘 봐서가 아니다. 절대.