일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- codeforces
- 기하 알고리즘
- 14179
- 2794
- 볼록 껍질
- 백준 온라인 저지
- IOI 2013
- BAPC
- boj
- convex hull
- 코드포스
- JOI
- Manacher 알고리즘
- 8192
- BAPC 2018
- acmicpc.net
- Divide and conquer optimization
- Implementation
- Z algorithm
- 기하
- Z 알고리즘
- ICPC 연습
- 구현
- JOI 2018
- 컨벡스 헐
- 세그먼트 트리
- Manacher's algorithm
- DP
- 그래프
- POI Solution
- Today
- Total
프로그래밍 연습장
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)$.
'문제 해결' 카테고리의 다른 글
ICPC Yokohama Regional 2018 (2) | 2020.07.20 |
---|---|
190720 팀 연습: BAPC 2018 (2) | 2019.07.21 |
180519 동아리 연습 문제 풀이 (0) | 2018.05.19 |
180428 동아리 연습 문제 풀이 (1) | 2018.04.28 |
180421 동아리 연습 문제 풀이 (1) | 2018.04.21 |