2022 SKKU 프로그래밍 대회 in 소프트의 밤 검수 후기

검수진 모집 글이 있길래 무지성으로 넣었더니 되었다. 아쉬웠던 점은, 시험기간과 제대로 겹쳐 시간을 많이 투자하진 못했던 것 같다. 그래도 오픈 전까지는 모든 문제에 AC 코드를 만들어 넣긴 했다.

 

대회 링크 : https://www.acmicpc.net/category/detail/3214

 

문제별 후기

 

A. 안녕 클레오파트라 세상에서 제일가는 포테이토

A번이다. A번답고 좋다.

 

B. 장인은 도구를 탓하지 않는다

검수할 때는 \(N=10\)인거 보고 무지성 완전탐색을 짰는데, 그냥 최솟값 빼고 다 곱하면 되는 것 같다.

 

C. 수렵의 시간이다!

하라는 대로 열심히 짜면 된다. 구현 문제는 짤 때마다 정말 화가 나는데, 티어를 높게 주지 못하는 점이 너무 아쉽다.

 

D. 양과 늑대

멋진 인터랙티브 문제이다. 제한을 보고 이분탐색처럼 하면 됨은 쉽게 알 수 있는데, 전형적인 이분탐색처럼 접근하기가 힘들다. 뭔가 쉽게 보지 못할 아이디어라 재미있었다.

 

E. 수열의 합

누적합 2개로 분리시킨 후, 더블 카운팅으로 세주면 \(O(N)\)에 문제를 해결할 수 있다. 익숙한 사람한테는 쉽고, 아니면 어려운 것 같다.

 

F. 수확의 시간이다!

파라메트릭임은 쉽게 알 수 있는데, TL 바운드가 빡세 뭔가 처리를 해 주어야 한다. 에디토리얼에는 hash map 써도 TLE라고 써 있는데, 정작 난 그냥 hash map으로 잘 풀었다.

 

G. 게이트웨이 정하기

비트별로 봐준 후, 트리에 0 혹은 1을 잘 칠한 후 각 개수를 구해 잘 처리하면 정답을 받을 수 있다. 교육적이고 좋은 문제라고 생각한다.

 

H. 현상금 헌터

가장 마지막으로 푼 문제이다. 순수 풀이 난이도는 솔직히 아래 문제들보다도 어렵다고 생각한다. DP식을 세우는 것과, 그것이 왜 잘 되는지, 그리고 약간의 구현적 테크닉이 필요한데, 다 흔한 유형은 아니라 매우 어려웠다. 검수 중 의견은 대부분 P4~5였는데 난 적어도 P3이라고 생각했고, 결국 P2를 주었다.

 

I. 전투 시뮬레이션

식 정리를 잘 하면 구간 안에서 특정 수에 가장 가까운 수를 찾는 문제가 되고, 이는 머지 소트 트리로 해결할 수 있음이 잘 알려져 있다.

 

J. 달나라에 사는 토끼와 우주에서 떨어지는 떡

사이클과 사이클이 아닌 부분을 나누어 잘 생각해주면 되는데, 구현도 꽤 많고 사고 과정도 그냥 복잡하다. 어렵지만 좋은 문제라고 생각한다.

 

K. 커모드 곰의 연어 사냥

제대로 된 증명을 하지 않더라도, 뭔가 단절점만 남기면 될 것 같다고 생각할 수 있다. 그 이후는 그냥 NIM 게임이다.

 

총평

문제 퀄리티가 다 (특히 뒤쪽 문제) 좋았던 것 같다. 좋은 대회 만들어주셔서 감사합니다~