UCPC 2023 예선
UCPC 2023 예선
www.acmicpc.net
서론
UCPC 2023 예선에 참가하였다.
팀원은 학교 친구인 bugsbunni22와 hyup98인데 두 명 모두 ps와는 거리가 멀다.
bugsbunni22의 역할은 영어 지문 해석이지만 UCPC에서는 영어 지문이 거의 나오지 않는다.
hyup98의 역할은 템플릿 코드 타이핑이지만 예선 대회에서는 미리 준비한 코드를 사용할 수 있다.
그렇다고 아무 것도 안 시키면 팀원들이 심심해할 듯 해서 가장 쉬운 문제인 A번을 던져주기로 하였다.
이후 계획은 딱히 생각하지 않았다.
D - 더 흔한 타일 색칠 문제
N × M 타일의 각 칸은 K × K 타일의 특정 칸에 대응한다.
각 칸별로 빈도수를 세면 된다.
00:06 AC
I - 자석
N극을 S극 왼쪽에 놓는다고 가정하자.
S극을 j번 칸에 놓는다면 N극은 j 미만인 i에 대하여 (A[i] + i * K)가 최대인 칸에 놓으면 된다.
N극을 S극 오른쪽에 놓는 경우는 배열을 뒤집은 후 동일한 방법으로 처리할 수 있다.
00:16 AC
K - 세미나 배정
이분 탐색
00:32 AC
A - 체육은 코딩과목 입니다
팀원 두 명에게 빨리 풀기 대결을 시켰다.
결과는 hyup98이 WA를 2번 받고 34분에 AC를 받았다.
비록 페널티를 많이 쌓긴 하였지만 좋은 경험으로 남았으면 한다.
00:30 WA
00:32 WA
00:34 AC
이후 C번이 mst 문제임을 파악하였지만 직감적으로 공식을 구하기 어렵다는 판단을 내렸다.
팀원들에게 공식을 찾아달라고 부탁하고 다른 문제를 읽었다.
하지만 인터넷 검색으로 나오는 대부분의 공식은 각도를 고려하지 않는 부정확한 공식이었다.
내가 직접 공식을 구해보려 하였지만 수학 젬병에 기하 젬병인 나는 뇌정지가 왔다.
아쉬움을 뒤로 하고 B번을 잡았다.
B - 물류창고
small to large
01:27 AC
팀원들이 던져준 공식은 여전히 틀렸고 나는 삼각함수가 포함된 공식을 찾아보라고 하였다.
이후 하나의 공식을 받았는데 공식이 잘못된 것인지 내 구현이 잘못된 것인지 계속해서 오차가 발생하였다.
시간은 흘러만 갔고 이대로라면 나락이라는 직감에 F번을 잡았다.
F - 응원단
각 단원을 다음과 같이 4가지로 분류할 수 있다.
- 홀수 행 홀수 열
- 홀수 행 짝수 열
- 짝수 행 홀수 열
- 짝수 행 짝수 열
주어지는 응원 패턴에 따라서 적절히 업데이트하면 된다.
응원 패턴에 따라서 홀수 행 단원이 짝수 행 단원이 되기도 하고 짝수 열 단원이 홀수 열 단원이 되기도 한다.
이 부분을 주의해서 구현해주자.
02:18 AC
C - 차량 모듈 제작
mst + 기하
나의 미숙한 기하 실력으로는 공식을 구할 수 없었는데 다행히 해외 사이트에서 공식을 찾았다.
02:23 AC
이후 에디토리얼을 보면서 공식 유도 과정을 공부하였는데 너무나도 간단하였다.
아마도 수학과 기하를 담당하는 뇌 파트가 뒤져버린 것 같다.
이후 H번을 잡았는데 관찰과 시간 모두 부족해서 풀지 못하였다.
H - 팔찌 (not solved)
각 문자열을 다음과 같이 정규화할 수 있다.
- 모든 문자가 동일해질 때까지 서로 다른 인접한 두 문자를 합친다.
- 문자열의 길이가 2 이하가 될 때까지 적절한 연산을 적용하여 문자열의 길이를 2만큼 줄인다.
- 문자열이 "GG" 또는 "BB"라면 적절한 연산을 적용하여 "RR"로 만든다.
모든 과정을 마치면 각 문자열은 "R", "G", "B", "RR" 중 하나가 된다.
이 과정을 잘 구현해주면 된다.
E - 반전수 (not solved)
어려운 수학 문제 같아서 바로 넘겼다.
G - 은하 온라인 마케팅 프로젝트 (not solved)
시간 제한 5초 보고 바로 넘겼다.
J - 다섯 용사의 검 (not solved)
시간 제한 5초 보고 바로 넘겼다.
결과
41등이라는 처참한 성적으로 마무리하였는데 하마터면 본선 진출에 실패할 뻔하였다.
패착은 크게 두 가지였다.
첫 번째는 팀원들에게 A번을 맡긴 것인데 대략 70분의 페널티를 받았다.
하지만 내가 풀었다고 하더라도 등수는 크게 바뀌지 않았을 것이다.
두 번째는 C번을 붙잡다가 B번과 F번의 페널티를 크게 늘린 것이다.
공식만 구하면 바로 풀 수 있다는 마음에 C번을 상당히 오래 붙잡고 있었다.
하지만 굳어버린 뇌는 삼각함수를 받아들이지 못하였고 여기서 큰 병목이 생겼다.
그나마 다행인 점은 코딩 실수를 하지 않아 추가적인 페널티는 받지 않았다는 것이다.
결론적으로는 본선에 진출하였고 수상 가능성은 전혀 없으므로 재밌게 즐기고 오려고 한다.
팀원들이 많이 심심할 것 같아서 둘이서 즐길 수 있는 게임을 생각해 오라고 하였다.
뭐 기껏해야 오목이지 않을까 싶은데 5시간을 잘 버텨주었으면 한다.
끝
끝