2020 선린 정보 알고리즘경시대회

올해 선린인터넷고등학교의 교내 정보경시대회를 출제하게 되었다. 출제는 김준원님, 권욱제님과 함께 했으며, 정종인님이 서버 관리를 맡아주셨다. 일정이 워낙 촉박해서 대회 진행에 있어 다소 아쉬운 점이 있었으나, 문제 자체의 질은 괜찮다고 생각한다.

 

간단한 문제 해설과 함께 본인이 출제한 문제에 대해서는 출제 의도, 본인이 출제하지 않은 문제에 대해서는 출제 의도가 아닌 예상 난이도를 적어둔다. 문제는 BOJ에서 해결할 수 있다.

문제 풀이

A. 헛간 청약

• 출제: wookje
• 예상 난이도: Bronze IV - Bronze III

정답이 최대 $N$임에 유의하여 해결하면 된다. $\lfloor W/L \rfloor \times \lfloor H/L \rfloor$가 가장 많이 등장한 오답 중 하나였다.

B. 소-난다!

• 출제: wookje
• 예상 난이도: Silver III - Silver I

비트마스킹을 이용하여 $2^N$개의 집합을 모두 순회하며 크기가 $M$인지, 합이 소수인지 체크해주면 된다. 어떤 수가 소수인지 체크하는데 있어 많이 하는 실수가 "소수의 제곱을 소수로 판별"하는 것인데, (대개 반복문의 종료조건이 잘못되어 발생) 이 부분에 유의해야 한다.

C. 수업

• 출제: junie
• 예상 난이도: Gold IV - Gold II

수강생들을 키 역순으로 정렬하고, $i$번째 수강생을 크기가 $k_i$ 미만인 팀 중 가장 크기가 큰 팀에 넣어준다. (그러한 팀이 없으면 새로운 팀을 만든다.) 이 과정을 반복적으로 수행하는 그리디 알고리즘을 통해 해결할 수 있다. 이분 탐색이나 균형잡힌 이진 트리 자료구조 등을 이용하여 효율적으로 구현하면 된다.

D. 소 운전한다.

• 출제: junie
• 예상 난이도: Gold II - Gold I

다익스트라 알고리즘을 돌리는 동시에 동적계획법 배열을 채워가며 해결할 수 있는 문제다. (1) 음식을 먹지 않고 특정 정점으로 가는 최단 경로의 길이와 (2) 음식을 먹고 특정 정점으로 가는 최단 경로의 길이를 메모이제이션 해주면 된다. 고 한다.

나는 그래프 층을 2개 쌓아서 풀었다.

E. 친구

• 출제: leejseo
• 출제 의도: Platinum IV - Platinum III

Ore's theorem을 증명하고, 이를 코드로 옮기는 문제이다. 출제 의도는 수학적 귀납법과 비둘기집의 원리를 이용해 해결하는 것이었으나, 실제 대회 참가자 중 구글링을 열심히 하여 해결한 사람도 있다. 이 부분은 나의 불찰이다.

 

증명의 경우, 수학적 귀납법과 비둘기집의 원리를 이용하여 할 수 있고, 이를 그대로 코드로 옮기면 $O(N^2)$ 시간 복잡도에 해결할 수 있다. 하지만, $\deg(x) \ge n/2$가 워낙 강력한 조건인 만큼, 이 부분을 활용하는 참가자들의 여러 좋은 휴리스틱 또한 통과할 여지를 남겨두고자 $N = 100$으로 설정했다.

 

원래는 $N = 1$이고, 답이 $-1$인 예제를 만들어 항상 가능하다는 부분에 대해 확신을 가질 수 없게 하려고 했으나, 좀 추한 것 같아서 그러지 않았다.

F. 실험

• 출제: leejseo
• 출제 의도: Diamond V

문제의 지문을 읽어보면 대놓고 2-SAT임을 드러내는 문제이나, 이를 아무 생각 없이 구현하면, $O(N^2)$개의 clause가 생겨 시간 초과를 받게 된다. 출제 의도는 Prefix or를 이용하여 하나의 그룹에서 최대 한 사람이 뽑힌다는 조건을 선형 개수의 clause만을 이용하여 구현하는 것이다. 이 테크닉에 대한 자세한 설명은 jh05013님 블로그에서 찾을 수 있다.

 

맺음말

선린인터넷고등학교와 어떻게 인연이 닿아 작년에는 알고리즘 토크쇼, 올해는 정보 경시대회 출제를 하게 되었다. 이 두 경험 모두 나에게 있어 값진 경험이었고, 다음에 또 좋은 인연이 생겼으면 좋겠다.