SCPC 2023 (예선, 본선) 후기

이번이 대학 막학기여서 마지막 SCPC였습니다.
알고리즘을 공부할 시간은 없었지만 당일 시험시간 동안만큼은 최선을 다해 열심히 풀어보았습니다.

1차 예선

1번 <증강현실 배달 안경>

간단한 식 하나면 끝나는 문제였습니다.

2번 <딸기 수확 로봇>

범위에 따라 케이스를 나누어 생각하면 어렵지 않게 스위핑으로 풀 수 있습니다.

3번 <장난감>

규칙을 떠올리면 간단하게 풀 수 있는 문제였습니다. 초기 상태에 따라 두 가지로 케이스를 나누어 시뮬레이션을 한 뒤에, KMP를 이용하여 최소 패턴 길이를 계산했습니다.

4번 <최적의 프로세스 수행 순서>

이 문제도 KMP를 조금 변형하여 활용하면 될 것 같아보였습니다.
근데 생각보다 잘 안됐고, 몇 번 틀리다가 포기했습니다.

5번

사실 3문제를 풀면 1차 예선을 통과한다는 것을 작년의 경험으로 알고 있었기에 4번을 포기하면서 5번도 포기했습니다.
다른 대회 프로젝트 마감과 소프트웨어 마에스트로 중간발표가 얼마 남지 않아서 많은 시간을 투자할 수는 없었습니다.
5번은 문제를 대충 봤을 때 어려워보였기 때문에 시간을 들여도 결과는 같았을 것이라고 생각합니다.

2차 예선

1번 <타이젠 윷놀이>

윷놀이판에서 말이 이동하는 방식을 함수로 미리 만들어두고, 최소 반복패턴을 찾으면 해결할 수 있습니다.

2번 <괄호 문자열>

스택을 이용해서 풀 수 있었습니다.
병렬로 된 연속쌍의 개수를 찾고, 그 값을 $\frac{n(n+1)}{2}$ 로 계산해서 더하기만 하면 됩니다.

3번 <루머>

이 문제는 정해가 도저히 생각이 안나서, 비트마스크를 이용하여 $O(2^n)$으로 최저 점수 45점만 받고 넘겼습니다.

4번 <막대기 연결>

이 문제 역시 정해가 생각이 안나 부분점수를 노렸습니다.
$n^2$짜리 DP테이블을 만들면 오프라인 쿼리 없이도 부분점수 180점을 받을 수 있었습니다.

5번 <스마트 아파트 건설>

이 문제도 부분점수를 노렸습니다.
단순히 next_permutation 을 사용해서 부분점수 60점을 받았습니다.

본선

1번 <돌 게임>

홀짝으로부터 규칙성을 찾아서 해결했습니다.
묶음 수 N과 각 돌의 수를 모두 XOR 계산해두었고,
돌이 짝수개인 수를 계산하여 이와 홀짝을 비교했습니다.

4번 <그릇>

규칙을 찾아내서 점화식을 유도해보았습니다.

$x_{ij}=2*x_{(i-1)j} + (i-2)*x_{(i-1)(j-1)}$

위 식이었는데, 이를 통해 $N^2$ DP 테이블을 만들어서 진행하려고 생각했습니다.
N<=5000 제한이었기에 시간복잡도 상으로 충분히 통과되지 않을까 생각했는데 왜인지 시간초과가 나왔습니다.
더 최적화된 점화식이 있는 것 같습니다.
결국 N<=400 의 부분점수만을 받았고,
아쉬움이 남아 대회가 끝날 때까지 계속 고민해보았지만,
끝내 점수를 다 받지 못했습니다.

끝

마지막 SCPC가 끝이 났고, 수상은 못했지만 본선에 참가할 수 있었던 것만으로도 충분히 만족스럽습니다.

이제 성인부 만들어주세요