2020 선린인터넷고등학교 정보 경시대회

올해 선린인터넷고등학교 정보경시대회를 1/3 정도 출제했다. 여러 아쉬움은 있지만 문제 자체는 좋은 편이고 풀이가 없으니, 풀이들을 작성한다. 돔저지로 진행했지만, 이번 주 안에 BOJ에도 문제들이 업로드될 것이다.

 

1. 헛간 청약

$\min(N, \lfloor \frac{W}{L} \rfloor \times \lfloor \frac{H}{L} \rfloor)$을 출력하는 문제이다. 출제 의도는 $\min(N,)$을 안 붙여서 뇌절하는 모습을 구경하는 것이다.

 

2. 소-난다!

$N$개의 원소들 가운데 $M$개를 고르는 모든 조합을 일일히 순회하는 것이 문제의 핵심. $M$개를 골라야 한다는 사실을 잠깐 가려두고 비트마스크로 모든 $2^N$개의 부분집합을 일단 보는 것이 가장 편할 것이다. 소수 판별은 에라토스테네스의 체를 쓰지 않고 심지어 naive한 $O(X)$의 방법을 사용하더라도 빠르게 잘 돌아간다.

 

3. 수업

수강생들을 키의 내림차순으로 정렬한다. 키가 가장 큰 수강생부터 키의 내림차순으로 보면서 한 명씩 팀을 꾸려나가는데, 각 수강생은 "크기가 $k_i$ 미만인 팀 중에서 가장 크기가 큰 팀"에 집어넣는다. 그런 팀이 없으면 새로 만든다. 그렇다. 그리디 알고리즘이다.

 

알고리즘의 정당성은 수학적 귀납법으로 증명한다. 한 가지 주장을 덧붙이면 증명하기 쉬워진다. 위 알고리즘으로 만들어지는 팀은, 가장 팀의 개수가 적을 뿐 아니라, 가장 크기가 작은 팀의 크기도 최소화된다.

 

위 알고리즘을 곧이곧대로 구현하면 $O(N^2)$의 알고리즘이 나온다. 이는 물론 시간 초과에 해당한다. 시간 복잡도를 줄여 보자. 먼저 위 풀이에서 '실제로 무슨 수강생이 무슨 팀에 들어가는지'는 중요하지 않다. 각 팀들의 리스트를 일일히 저장하는 대신 '팀의 크기'들을 나타내는 정수들을 저장하고, 매번 '$k_i$ 미만인 정수들 가운데 가장 큰 정수'를 하나씩 증가시켜준다. '$k_i$ 미만인 정수들 가운데 가장 큰 정수'를 이분 탐색을 이용해 구현하거나, std::set과 같은 자료형에 넣으면 이 연산이 $O( \log N)$에 처리 가능해지고, 총 시간 복잡도는 $O(N \log N)$이 된다.

 

4. 소 운전한다.

Dijkstra 알고리즘 연습문제이다. 욱제님 말로는 '다익스트라 DP'라고, 이미 모두가 알고 있다고 했지만 나는 그런 용어를 처음 들어보았다. 머쓱..ㅎㅎ,, 다익스트라 DP는 대충 $dp[0][x]$ := 음식 안 먹고 $x$번 정점으로 가는 최단거리, $dp[1][x]$ := 음식을 먹고 $x$번 정점으로 가는 최단거리로 정의하고 한 번의 dijkstra로 모든 $dp$ 배열값을 채우는 방법이다. 머 정확히는 잘 모르겠지만 그런가보다.

 

내가 의도한 풀이는 각 정점을 두 개로 쪼개는 것이다. 같은 정점을 1층에 하나, 2층에 하나 만든다. 그리고, $x$번 정점에서 $y$번 정점으로 가는 길이 $t$, 맛 $k$의 간선 또한 다음과 같이 3개로 쪼갠다.

 

• 1층의 $x$번 정점에서 1층의 $y$번 정점으로 가는 길이 $t$의 간선
• 2층의 $x$번 정점에서 2층의 $y$번 정점으로 가는 길이 $t$의 간선
• 1층의 $x$번 정점에서 2층의 $y$번 정점으로 가는 길이 $t-k$의 간선

 

저렇게 보면 '돈까스를 먹는다'를, '1층에서 2층으로 올라간다'로 바꾸어 쓸 수 있다. 그러면 문제는 1층의 1번 정점에서 2층의 $2, \cdots, N$번 정점으로의 최단 거리를 그냥 구하는 걸로 바뀐다. 물론, 음수 가중치의 간선은 기분이 나쁘니, 1층에서 한 번, 2층에서 한 번 dijkstra 알고리즘을 돌리면 되겠다.

 

어떤 참가자는 이제 dijkstra 알고리즘을 사용하면 되는 상황에서 SPFA 알고리즘을 박았다. ㅎㅎ;;

 

5. 친구

문제에서 주어진 조건이 매우 널널해서 어떻게 잘 끼워넣으면 될 것 같이 생겼다. 실제로 그렇다. 그냥 아무 배치나 준비한 다음에 서로 싫어하는 사람이 붙어있으면 떼어주기로 하자. 문제에서 불가능하면 $-1$을 출력하라고 했지만, 불가능한 경우는 절대 없음은 손으로 몇 번 돌려보면 쉽게 간파할 수 있을 것이다.

 

방법은 매우 다양하다. 의도된 풀이는 다음과 같다: $x$의 오른쪽에 있는 사람을 $right(x)$라고 부르자. 만약 $x$와 $right(x)$가 서로를 싫어한다면, $x$ 옆에 $right(x)$ 대신 $x$를 좋아하는 사람을 붙여둬야 할 것이다. 이 때, 다음과 같은 사람 $y$가 항상 존재함은 증명 가능하다:

 

$x$와 $y$가 서로 좋아하고, $right(x)$와 $right(y)$가 서로 좋아한다.

 

이제, $x$와 $right(x)$ 사이를 끊고, $y$와 $right(y)$ 사이를 끊고, 한 쪽을 뒤집어서 이어붙인다. 즉, 이제는 $x$ 옆에 $y$가, $right(x)$ 옆에 $right(y)$가 오게 된다. 이제, $x$ 오른쪽에 $x$를 좋아해주는 사람이 붙었을 뿐 아니라, $right(y)$ 오른쪽에도 $right(y)$를 좋아해주는 사람이 붙었다.

 

이 과정을 $N$번 반복하면 언제나 모든 인접한 쌍이 서로를 좋아하는 배치가 완성된다. 시간 복잡도는 $O(N^2)$이지만, 참가자의 뇌절을 유도하기 위하여 $N$의 제한은 작게 설정되었다.

 

6. 실험

조건 1이 없고 조건 2만 존재한다면, 너무나 대놓고 2-SAT 문제이다. 사실 조건 1도 2-SAT의 향기가 강하게 난다. 조건 1을 몇 개의 2-SAT clause로 바꿔서 다같이 2-SAT 알고리즘을 돌리면 될 것 같다.

2-SAT을 해결하는 방법에 대한 이야기는 생략한다. 문제의 핵심은 조건 1인 "$k$명의 사람들 $a_1, \cdots, a_k$ 중 한 명만을 골라야 한다"를 $O(k)$개의 clause로 나타내는 것이다.

이를 위해 $k$개의 가상 변수를 만든다.

• $b_1 = a_1$
• $b_2 = a_1 \lor a_2$
• $b_3 = a_1 \lor a_2 \lor a_3$
• ...
• $b_k = a_1 \lor ... \lor a_k$

그리고, $a_i \rightarrow b_i$, $b_i \rightarrow b_{i+1}$, $b_i \rightarrow \lnot a_{i+1}$의 세 가지 조건을 나타내는 간선을 추가하면, $k$개의 변수와 $3k$개의 clause를 추가하여 문제를 해결할 수 있다. 시간 복잡도는 $(A+B) \log (A+B)$.