SCPC 2023 본선 후기

캡처를 못 해 아무 사진으로 대체합니다

서론

9월 16일, SCPC 본선에 참여했습니다. 소멤 혜택을 제대로 누리기 위해서는 이번 대회에서 상을 받아야 했기에 각오를 좀 한 채로 쳤습니다. 대회 전에는 플레 알고리즘 복습을 했지만, 작년부터 바뀐 SCPC의 기조가 그대로 유지될 것이라 생각했기 때문에 이보다는 플랜디를 돌리는 것에 조금 더 중점을 두었습니다.

 

대회 중

 

~0:09

전날 잠을 제대로 자지 못해 약간의 걱정을 안고 문제를 열었습니다. 우선 작년처럼 배점이 같지는 않았고, 2=4<3인 점이 눈에 띄었습니다. 우선 1번을 열었습니다. 공책에 케이스를 써 보니 별 반례 없이 간단한 규칙이 존재하는 것 같아 짜서 맞았습니다. 지난 2년은 1번을 풀지 못하거나, 힘들게 풀었다는 점에서 괜찮은 시작이라는 생각이 들었습니다.

 

~1:25

2~4번 배점이 특이해서 세 문제를 모두 읽었습니다. 각 문제에 대한 소감은 이랬습니다:

2: 이 문제가 생각났다. 다만 제한을 보니 그리디는 아니고, DP같았다. 하지만 1번에서 이미 제한 낚시를 당했기에 단정지을 수 없었다.

3: 이 문제의 풀이를 알아야 할 것 같았다. 허나 저 문제는 방학때 큐에 넣어 놨다 결국 풀지 못하고 유보한 문제였고, 결과적으로 풀이를 몰랐기에 15점 초과의 점수를 받긴 힘들어 보였다.

4: 대충 코포나 ARC에 잘 나오는 조합 DP 같아 보였다.

세 문제를 모두 읽고 난 후 4번 만점자가 나오기 시작했길래 4번을 잡았습니다. 점화식을 열심히 써 봤지만 너무 더러운 \(O(N^4)\)밖에 찾을 수 없었고, 만점자 수에 의거해 브루트 포스를 짜 찍어보았습니다. 다행히 규칙을 빠르게 찾을 수 있었고 2번 정도 틀린 끝에 만점을 받을 수 있었습니다. 저는 대회 중 큰 수를 넣는 방식으로 접근했는데, 작은 수를 넣는 방식으로 생각하면 쉽게 풀린다고 합니다.

 

~2:18

이후 5번을 마저 읽었습니다. 총 20점은 쉽게 긁을 수 있었고, 선인장 DP를 짜면 100점이 넘는 점수를 받을 수 있었습니다. 며칠 전 선인장의 독립집합 문제를 풀고 왔기 때문에 선인장 구현에 어느 정도 자신이 있었고, 이를 짜는 것을 대회 중 최종 목표로 잡았습니다. 그 전에, 우선 긁을 수 있는 섭태를 먼저 긁기로 했습니다. 다익스트라를 짜 5-1의 5점을 긁었습니다. 지금 보니 4번 해결 시점으로부터 50분이나 지났는데, 멍 때리는 시간 조금 + 애초에 BCC까지 짤 것을 전제로 한 후 코딩에 들어갔기 때문에 구현 시간이 좀 길었던 것 같습니다.

 

~3:00

그 다음에는 2-1의 61점을 긁으러 떠났습니다. 좀 귀찮은 부분들이 있긴 했지만 어렵진 않았고, 몇 번의 시행착오 끝에 61점이 나와야만 하는 코드를 완성할 수 있었습니다. 그러나 여기서 문제가 발생하는데, 61점이 뜨지 않습니다. 섭태 처리도 잘 했고, 아무리 봐도 틀린 점이 없어서 10분간 같은 코드만 보다 정신을 차리고 다른 테케를 긁으러 떠났습니다.

 

~3:12

브루트 포스로 3-1의 15점을 긁었습니다.

 

~3:40

그동안 짠 선인장 코드를 모두 포기하고, 15점짜리 5-2 트리 섭태를 긁었습니다. 풀이 자체는 플5의 Rerooting DP를 그대로 짜면 되어서 어렵지 않았습니다.

 

~3:49

다시 2-1 코드를 보러 갔습니다. 아무리 봐도 틀린 점이 없어 최후의 발악으로 '\n'을 endl로 바꿨는데....

다행히 61점을 볼 수 있었습니다. 비로소 숨을 좀 돌릴 수 있었습니다.

 

~4:00

5-3의 \(N=M\) 섭태를 긁다 물리적으로 불가능함을 깨달았습니다.

 

최종 점수 = 100 + 61 + 15 + 200 + 20 = 396

 

대회 후

대회 직후 포스텍의 다른 본선 진출자 선배들과 이야기를 나눴습니다. 작년에 ICPC를 같이 나간 두 선배는 이미 SCPC 수상자이기에 더 큰 상을 노리기 위해 300점 쯤에서 멈춘 것 같았고, 대신 재야의 고수이신 복학생 kkpos0206 선배가 400점 중반의 굉장히 높은 점수를 받았습니다. 따로 연락을 할 수 있는 사람은 더 없었기에, solved.ac 디스코드를 슬쩍 보았습니다. 61점을 긁은 사람이 생각보다 없었고, 300점대 초중반에 점수가 몰려있다는 사실을 알 수 있었습니다. 그 와중 떠오르는 신성 hijkl2e님의 점수와 1점 차이가 나는 점이 신기했습니다.

 

대회 직후에는 5등상 컷 쯤인 줄로 알아 무서웠지만, 이후 여러 결과를 종합했을 때 kkpos 선배는 4등상 중반, 저는 5등상 초중반임을 유추할 수 있었습니다.

 

대회 결과 및 후기

비교적 편한 마음으로 시상식에 들어갔습니다. 4등상에 대한 일말의 기대가 있었지만, 올해부터 성적순으로 바뀐 시상자 발표 순서는 제가 5등상 2등임을 말해주었습니다. 허나 점수 분포를 대략 보니 5-3을 풀었어도 5등상이고, 2-1을 못 풀었어도 5등상인 것 같아 이제는 그저 감사할 따름입니다. kkpos 선배는 예상대로 4등상을 수상하셨습니다. 아마 내년 ICPC를 같이 나가게 될 것 같은데, 요즘 퍼포먼스가 굉장히 좋으셔서 내년 성적에 기대를 좀 걸고 있습니다.

 

허나 월파를 노렸던/노릴 위치에서 5등상은 아쉬운 퍼포먼스임은 사실입니다. 복기를 해 보자면, 확실히 더 긁기 쉬운 2-2와 3-2(아마도)를 버리고 선인장을 짜기로 결심한 것이 패착이었던 것 같습니다. 또한, 3번 원본 문제의 풀이를 알았다면 시작점이 달랐을 수 있다는 점에서 공부를 더 열심히 해야겠다는 생각 또한 들었습니다.

 

국내 PS 대회 중 규모가 큰 4개의 대회를 꼽자면 ICPC, UCPC, SCPC, 현대모비스 대회가 주로 꼽히는데요, 이번 SCPC를 계기로 아무튼 네 대회에서 모두 본상 수상 경험이 생겼습니다. 다만 UCPC는 버스를 탄 감이 좀 많이 있고, SCPC는 개인적으로 퍼포먼스에 만족할 정돈 아니었기 때문에 내년에 더 좋은 결과를 거둘 수 있으면 좋겠습니다.

 

수상하신 분들 모두 축하드립니다!