2022 경인지역 6개 대학 연합 프로그래밍 경시대회 shake! 후기

결과는 2위를 했다. 목표는 10위안에 들어보자 였는데 생각보다 결과가 너무 잘 나와서 뿌듯하다.

 

작년에 인하대 IUPC에서 선발되어서 2023년 3월 11일에 열린 2022 shake! 대회에 참여했다.
올해는 온라인으로 시험을 봤는데 항상 알고리즘을 공부하던 환경에서 시험을 보니까 더 좋았다.
결론적으로 이번 대회에서 A B C D E F G, 7문제를 풀었다.
 
까먹기 전에 문제에 대한 후기를 작성하고 싶어서 시험 끝나고 5시간 정도의 휴식을 가진 뒤 작성하고 있다.
 
A번 문제는 몇 번 이길 수 있는지 세는 거였고 자신보다 낮은 애들을 최대한 살리면서 진행하고
사라지면 반전 연산을 사용하는 게 답이었다. 그럭저럭 쉽게 풀었다.
 
B번 문제는 1부터 k까지의 주어진 소수에 해당하는 인수의 개수를 구하는 문제였다.
10분 정도 헤매다가 그냥 소수를 곱해 가면서 k를 나눈 값을 답에 더하면 되는 문제였다.
조금 헤맨 게 아쉽지만 이 문제도 나쁘지 않은 시간에 풀었다.
 
C번 문제는 분리집합을 3번 사용해서 그룹을 잘 쪼개는 문제였다.
구현에 시간이 생각보다 오래 걸렸기 때문에 조금 아쉽지만 그래도 그럭저럭 잘 풀었다.
 
D번 문제는 몇 번 틀리고 풀었는데 샘플 테스트코드가 많이 열악하기도 했고 이 문제를 구현할 때 실수를 좀 많이 했다.
지면이 오름차순 일 경우 그냥 아랫줄부터 한 줄씩 채워나가면서 세면 되고 (평탄해질 때까지) 오름차순이 아닐 경우 지면이 평탄해질 때까지 일단 채우면 된다. 지면이 평탄하면 그냥 주기적으로 답이 1씩 증가한다. 어느 정도 삽질 하다가 풀었다.
 
E번은 미리 현재칸부터 한 칸씩 전진해서 땅에 도달하면 시간이 얼마나 걸릴지 전부 구해 놓는다.
그리고 한 칸씩 전진하면서 점프했을 때의 최솟값 + 현재까지 온 시간을 이용해서 답을 계속 최솟값으로 갱신해 준다.
점프했을 때 최솟값을 n이 500밖에 안 돼서 그냥 세그먼트 트리를 썼는데 시간 초과가 떴다. ㅋㅋㅋ
사실 생각해 보면 어차피 세그먼트 트리 쿼리 l, r 중에서 l이 항상 1이기 때문에 그냥 prefix min으로 구해놔도 된다.
세그먼트 트리 지우고 다시 구현하니 맞았다. 일단 세그먼트 트리로 뇌절하느라 시간이 많이 소요됐다. 좀 아쉬운 부분이 있지만 그래도 잘 푼 것 같다.
 
F번은 제일 마지막에 풀었고, 푼 사람이 두 명 밖에 없었는데 사실 굉장히 규칙 찾기가 어려웠다. 이 문제를 1시간 정도 본 것 같은데 40분 정도는 풀이가 다른 길로 세다가 마지막 20분 남기고 풀이가 생각났다. 왼쪽에 두 개를 붙이고 오른쪽부터 2칸씩 건너뛰면서 붙여주면 홀 짝으로 2개씩 생성할 수 있다. 이 관찰만 잘한다면 풀 수 있는 문제였다. 1시간 정도 시간을 투자해서 풀었지만 어려웠던 문제인 만큼 나쁘지 않게 풀었다고 생각한다.
 
G번은 트리에서의 다이나믹 프로그래밍이었는데 뭔가 구현이 잘 안 돼서 굉장히 힘들었던 문제다. 다 풀었는데 디버깅하느라 시간을 30분 넘게 사용했다. 어떤 정점에서 모든 정점까지의 거리의 합을 전부 저장해 놓는다면 답은 구하기 쉬워진다. 이번 대회에서 가장 힘들게 푼 문제였고 이 문제를 푸는 그때 당시를 생각해 보면 좀 끔찍하다. ( 풀었는데 왜 자꾸 값이 이상하게 저장되었기 때문 )
 
F번을 3분 남기고 풀어서 사실 H번부터는 문제를 읽지도 못했다. 1등은 H까지 풀었던데 아마 시간이 좀 더 있었더라면 (? ) H 번이랑 J번도 풀 수 있었지 않았을까 싶다.
 
요즘 지난 코드포스 세트 풀면서 최대한 D ~ E 까지는 풀이 안보고 몇시간이 걸리든 생각해 내서 푸는 연습을 하고 있는데
이 방식이 조금 도움이 된 듯 하다.
 

shake! 경인지역 6개대학 연합 프로그래밍 경시대회