2023 SCPC 2차 예선 후기

후술할 이유로 대회 페이지를 캡처하지 못해 MyGround로 대체

역시나 잘하시는 분들이 자세한 풀이를 많이 써 주셨기 때문에 간단하게만 기록합니다.

 

09:00 ~ 10:08

전날 좀 늦게 자서 비몽사몽한 상태로 눈을 떴다. 1번을 열었는데, 열자마자 PTSD가 왔다. 그 이유는 1학기 팀 연습 때 10번을 틀려 "오렌지도 10번 틀리는 문제"로 한동안 놀림감이 되었던 실버 문제 와 같은 그림이 있었기 때문이다. 그 때의 기억을 떠올리면서 열심히 짜서 냈는데, 30분이나 검토를 했음에도 불구하고 풀테가 안 긁히길래 당황했다. 긁힌 섭태가 좀 이상해서 문제를 다시 봤더니 완주를 하면 말을 재배치한다는 내용을 고려하지 않았다는 사실을 깨달았다. 이와 더불어 몇 가지 잡다한 버그를 고쳤더니 100점을 받을 수 있었다.

 

10:08~14:00

개인 일정으로 인해 잠시 자리를 비웠다. 시간 제한이 있는 대회에서 자리를 비우는게 리스크있어 보이지만, 그동안의 SCPC 경험을 통해 컴퓨터 앞에 있어봤자 제출 횟수만 까먹을 것이라는 확신이 있었기 때문에 별 상관 없었다. 대신 이 동안 2~3번을 읽고 생각했다. 2번은 스택을 잘 관리하면 될 것 같았고, 3번은 대충 DP 같았다. 이 정도만 생각해놓은 후 다시 컴퓨터를 잡았다.

 

14:00~14:20

2번 코딩을 시작했다. 대충 괄호를 닫을 때 안에 있는 가장 큰 괄호 문자열 덩어리의 수를 \(x\)라 하면, \(x \choose 2\)를 더해주면 된다. 다만 주어지는 문자열에 괄호가 두 종류이고 올바른 괄호 문자열이 아닐 수 있어서 구현을 좀 주의해야 한다. 다행히 1번 틀리고 빠르게 맞았다.

 

14:20~16:17

이후 3번을 잡았다. 다행히 처음 생각한 DP 점화식이 맞아서 세제곱 풀이를 빠르게 찾을 수 있었다. 간단히만 설명하자면, \(DP[i][j]\)를 \(i\)번째 자리까지 \(j\)개를 선택했을 때 최종적으로 전염되는 사람 수의 최댓값으로 하고, DP 전이는 두 인덱스 사이 2의 개수에 따라 경우를 잘 나누어주면 된다. 약간의 고난과 3번의 제출 끝에 세제곱 섭태를 먼저 긁었다. (오만하게도, 이때부터 LCK를 같이 보느라 시간이 조금 지체된다)

 

16:17~18:44

공책과 씨름한 결과 DP 식을 제곱으로 줄였다. 다만, 누적 합 배열 2개와 덱 1개가 필요했다. 코스트가 컸지만 더 줄이는 방법을 모르겠어서 바로 구현에 들어갔다. 겨우겨우 다 짜서 냈더니 TLE를 받았고, 바로 \(N \leq 1000\)만 보도록 고쳐주었더니 0점을 받았다. 이러다간 진짜 제출 횟수로 망하겠다 싶어서 스트레스 테스트를 짜 열심히 돌린 후 180점을 받을 수 있었다. 코드는 분명한 \(O(N^2)\)이었지만 아마 상수로 터진 것 같았다. 여기까지 3번 제출을 8번 사용했다.

 

18:44~19:06

4, 5번 섭태를 긁으면서 머리를 식히기로 했다. 다행히 풀태 직전 섭태가 다 골드급이었고, 빠르게 모두 긁었다.

 

19:06~20:00

3번을 조금 최적화한 후 제출했는데 여전히 TLE를 받았다. 1번 남은 기회를 소중히 쓰고자 저녁을 먹으며 아이디어를 생각했다. 다행히, 그리디한 발상을 섞으면 상수가 제일 큰 덱을 없앨 수 있을 것 같았다.

 

20:00~20:59

코드에서 덱을 없앤 후 \(N=5000\) 데이터를 만들어 돌려 봤는데 0.6초 정도가 나왔다. 이게 3개 있을 수 있고, 전체 시간제한이 1.5초라 조금 애매하다고 생각해 남은 시간동안 계속 최적화를 시도했다. 하지만 별 다른 방법이 보이지 않았고, 끝내 마지막 남은 제출 버튼을 눌렀다.

정말 다행히도 300점을 받았고, 대회를 무사히 마무리할 수 있었다. 원래 집중력이 별로라 대회에서 버저비터를 친 적이 잘 없는데 중요한 대회에서 한 번 터트리니 정말 짜릿했다.

 

요새 PS를 좀 쉬었더니 폼이 떨어진 것이 느껴져 걱정이 많았는데, 과정이 어떻든 아무튼 높은 확률로 본선에 진출하게 될 것 같다. 올해는 꼭 SCPC 무관을 탈출했으면 한다.