대회후기: SCPC 2023 Rounds 1 & 2

입대를 한 2021년 이후 전반적으로 competitive programming 공부를 하지 않은 것이 사실이다.

그럼에도 불구하고 대회를 참여해서 손해볼 것은 없기에 SCPC를 다시 한번 신청하였다.

 

결과적으로 망하기는 했는데(나는 SCPC류의 well-known 문제들을 풀어내는 능력보다 이전 Google Code Jam 느낌의 ad hoc 문제에 더 강하다 - 그냥 공부를 안해서 그럴지도) 기록은 남긴다.

 

사실 요즘 기록을 남기는 것을 많이 소홀히 하고 있다.

대회 기록이 밀림은 물론이고, 평소 열심히 쓰던 일기와 강의 평가 또한 밀렸다.

뭔가 기록을 하자니 밀린 기록들부터 다 작성해야 할 듯한 기분이고,

또 기록을 퀄리티 높게 하려고 하다보니 부담이 되어 자꾸 미루게 된다.

 

그래서 그냥 앞으로는 퀄리티는 갖다버리더라도 기록을 어떻게든 남겨야겠다.

 

대회를 치룬 지 이미 한달이 넘은 시점이고, 아직 대회 문제가 공개된 것도 아니라서 내가 작성해둔 코드를 보고 회고한다.

 

Round 1

증강현실 배달 안경

Trivial한 brute force 문제였던 것으로 기억한다.

 

딸기 수확 로봇

1차원 딸기밭에서 원점에서 출발, 정해진 거리를 이동하며 최대한 많은 딸기를 수확하는 문제였던가?

원점에서 왼쪽으로 $a$, 오른쪽으로 $b$만큼의 범위 내에 최대한 많은 딸기가 들어오도록 하면 되는 문제인데, 이 범위를 two pointer로 잡아서 이동시키면 된다.

 

장난감

원형으로 배치된 칸에 구슬들이 들어있고, 매 차례 각 칸의 최상단 구슬이 한칸 옆으로 이동하는 구조였었다.

이 과정을 반복하다보면 특정 상태들이 주기적으로 반복되는데 이 주기를 찾는 문제였을 것이다.

조금 생각해보면 구슬들이 결국 퍼져서 (구슬 수가 충분하다면) 빈 칸이 다 사라짐을 알 수 있다.

이 이후에는 구슬 배치 전체가 회전하는 모양이므로 주기를 구할 수 있다.

 

구슬이 다 퍼진 이후의 주기는 KMP를 이용하면 구할 수 있고, 이 부분은 구현하여 제출했다. (아직도 KMP 짤줄 몰라서 구글링해서 참고)

그런데 구슬이 다 펴지는 시뮬레이션을 너무 복잡하게 생각해서 결국 대회 시간 내에 구현하지 못했다.

부분점수만 받았다.

Round 2

타이젠 윷놀이

말을 이동시킬 distance들의 배열이 주어지고, 이 배열을 반복할 횟수가 주어졌을 때, 몇 개의 말이 윷놀이를 마치고 들어오는지 세는 문제였다. 윷놀이 판의 각 시작 위치마다, 해당 배열을 한번 순회한 이후, 몇개의 말이 순회를 완료하고 마지막에 말의 위치가 어떻게 되는지 미리 계산해둘 수 있다. 이러한 전처리를 마치면 이제 해당 배열을 1회 반복하는 연산은 $O(1)$에 가능해진다. 따라서 해당 배열을 여러 번 반복했을 때의 시뮬레이션을 $O(n)$으로 할 수 있다.

윷놀이 판 시뮬레이션 코딩이 제일 오래걸리는 문제였다.

 

괄호 문자열

두 종류의 괄호로 이루어진 괄호 문자열의 부분 문자열중 balanced인 문자열의 개수를 세는 문제이다.

사람마다 조금씩 다르게 푼 것 같은데 나는 못풀었다.

바보.

 

그냥 하고싶은 말

또 본선 광탈.

왜이렇게 못하지 ㅋㅋ

평소 공부도 안하면서 대회 날먹하려고 하지 말자.