2023 IUPC (인하대학교 프로그래밍 대회) 출제 후기, 해설

작년에 왔던 화석 (진짜 화석임)이 죽지도 않고 또 와서 문제를 출제하고 있다.

이번에도 오프라인으로 개최했는데, 예산 지원을 많이 받아 풍선을 모두에게 나눠 줄 수 있었다.

대회 진행중 나는 시험장 바깥에서 모두에게 나눠줄 헬륨 풍선을 제작하는 막노동을 담당(?)했는데, 처음에 A번 문제 솔브가 너무 많아서 바빴던것 빼고는 재미있게 시험장의 열기를 느낄 수 있었던 것 같다.

주 8일 휴가가 아니라 주 8일 노동을 하고 있다. 다음에는 진짜로 몸으로 하는건 후배들 시킬것이다.

다음은 각 문제들의 출제 의도와 해설에 대해 간략하게 설명한다.

A. 모비스

https://www.acmicpc.net/problem/28074

28074번: 모비스

주어진 문자열에 포함된 알파벳 대문자들을 이용해 MOBIS를 만들 수 있으면 "YES", 그렇지 않으면 "NO"를 출력한다.

www.acmicpc.net

적어도 1솔씩 하라고 준 문제이다.

모비스에서 우리의 풍선을 사줬다. 고마워요!

B. 스파이

https://www.acmicpc.net/problem/28075

28075번: 스파이

첫째 줄에는 민겸이가 임무를 수행하는 총 일수 $N$과 민겸이가 얻고 싶은 최소 기여도 $M$이 공백으로 구분되어 주어진다. 둘째 줄에 민겸이가 정보 수집 임무를 수족관, 시청, 학교에서 수행했

www.acmicpc.net

완탐 문제를 하나 넣기 위해 제작한 문제이다.

황혼..이 아니라 민겸이가 할 수 있는 일이 6가지이고, 최대 8일간 일을 하니 $6^8$ 완전탐색을 돌리면 된다.

B2. 스파이 (Hard)

https://www.acmicpc.net/problem/28084

28084번: 스파이 (Hard)

www.acmicpc.net

오픈 컨테스트를 위한 Hard 문제 제작에 이 문제가 선정되었다.

우선 이 문제는 이쁜 $O(NM)$ DP 풀이가 있었는데, 그걸 위해 일부러 Hard로 만들기에는 너무 난이도가 낮은것 같아 $N$을 더 키우기로 했다.

그러면 $K$일째의 DP테이블 과 $(K+1)$일째의 DP테이블 사이의 관계를 선형결합으로 나타낼 수 있기 때문에 행렬의 곱셈으로 나타낼 수 있고, 거듭제곱을 $\log N$에 해서 빠르게 답을 계산해 낼 수 있다.

이 때 행렬의 크기를 가장 크게 구현하면 $6M \times 6M$이고, 행렬 곱셈으로 인한 $(6M)^3$이 충분히 돌아가도록 $M$의 범위를 조절했다.

C. 멀티탭 충분하다

https://www.acmicpc.net/problem/28076

28076번: 멀티탭 충분하다

역사와 전통의 인하대학교 PS소모임 CTP는 스터디를 위해 멀티탭 세팅을 수없이 하여, 이제 멀티탭을 가지고 놀 정도의 수준이 되었다. 말 그대로 가지고 놀고 있는데, 2구부터 108구까지 다양한

www.acmicpc.net

예전에는 멀티탭이 부족했었는데 이번에는 멀티탭이 정말 충분하다.

저 각도가 30도가 아니라 90도라고 생각해보자. 그러면 멀티탭이 가로와 세로로 번갈아서 꽂힐 것이고, 최대 2개의 멀티탭만이 눈에 보이도록 멀티탭을 적절하게 꽂을 수 있음을 쉽게 생각할 수 있다.

그러면 멀티탭을 정렬해서 가로로 가장 긴것 하나와 새로로 대충 $\frac N2$번째 정도에 있는 멀티탭 하나만 보이게 하고, 구멍 1개가 겹치니까 1을 빼면 될 것이다.

각도가 30도로 바뀌면 눈에 보이는 멀티탭의 수가 2개가 아니라 3개로 바뀔 뿐 풀이가 똑같다. 대신 예제 1에서 친절하게 보여줬듯이 이번에는 최대 구멍 3개가 겹치게 된다.

좋은 애드혹 문제였다고 생각한다.

D. 사탕 팔찌

https://www.acmicpc.net/problem/28077

28077번: 사탕 팔찌

사탕 팔찌를 완성할 수 있다면, 첫째 줄에 "YES"를 출력하고, 둘째 줄에 사탕 팔찌를 구성하는 사탕 묶음을 차례대로 공백으로 구분하여 출력한다. 가능한 답이 여러 개라면, 그 중 아무거나 하나

www.acmicpc.net

출제 의도는 올솔브 방지이다.

각 사탕 묶음을 하나의 정점으로 생각하고, 이을 수 있는 두 사탕 묶음 사이를 간선으로 하는 그래프를 생각해 보자.

그러면 이 그래프에서 적절한 해밀턴 회로를 하나 구하는 문제로 바뀐다.

하지만 해밀턴 회로는 NP-Hard이다. 어떻게 하지?

비슷한 문제인 오일러 회로는 DFS와 링크드 리스트로 푸는 웰노운 풀이가 있으니 이걸 이용해 보자.

오일러 회로는 모든 간선을 한번씩 방문하는 회로를 구하는 문제이니, 원래의 정점을 간선으로 바꿀 수 있는지 생각해 본다.

ABCD - BCDE - CDEF 와 같은 그래프가 있었다고 가정하자.

ABCD와 BCDE의 공통 부분 사탕 묶음은 BCD이고, BCDE와 CDEF의 공통 모시깽이는 CDE이다.

간선 BCD와 CDE를 동시에 가지는 정점은? BCDE가 유일하다는 사실을 알 수 있다.

그러면, 사탕 $K-1$개 만을 이용하는 모든 부분 사탕 묶음을 새로운 정점으로 해서 다시 그래프를 만들어보자. 이번에는 간선이 각각의 사탕 묶음을 나타내도록 그래프를 만들 수 있다.

이제 웰-노운인 오일러 회로 문제가 되었으니 풀면 된다. 방향 있는 오일러 회로 문제도 방향 없는 오일러 회로와 같은 방식으로 풀린다.

E. 중력 큐

https://www.acmicpc.net/problem/28078

28078번: 중력 큐

처음에 왼쪽이 큐의 뒤, 오른쪽이 큐의 앞인 가로 방향의 빈 큐가 존재한다. 이 큐에서 공이나 가림막을 하나씩 큐의 뒤에 삽입하거나, 큐의 가장 앞에 있는 공이나 가림막을 꺼낼 수 있으며, 큐

www.acmicpc.net

기본적인 자료구조를 잘 알고 있는지 확인하는 문제이다.

큐가 돌아가면서 큐의 앞과 뒤에서 push와 pop이 이루어진다. 그러면 deque으로 풀린다는 사실을 알면 된다.

공과 가림막이 들어온만큼만 빠져나가기 때문에 중력으로 인해 떨어질 때 하나하나 시뮬레이션 해도 된다.

공과 가림막이 push와 pop 될 때 남아있는 개수만 실시간으로 갱신해 주면 된다.

본 대회에서는 다 풀어놓고 빠른 입출력을 안써서 시간초과가 난 사람들이 꽤 있어서 안타까웠다.

F. 배 옮기기

https://www.acmicpc.net/problem/28079

28079번: 배 옮기기

치훈이는 배 $N$척을 강 건너편으로 옮기려고 한다. 강을 건너가거나 건너오기 위해서는 치훈이가 가지고 있는 배를 운전하여 건너야 한다. 배의 크기가 $X$라고 할 때, 치훈이가 그 배를 운전

www.acmicpc.net

매우 웰노운인 문제이다.

https://en.wikipedia.org/wiki/Bridge_and_torch_problem

Bridge and torch problem - Wikipedia

From Wikipedia, the free encyclopedia Logic puzzle The two solutions with the vertical axis denoting time, s the start, f the finish and T the torch The bridge and torch problem (also known as The Midnight Train[1] and Dangerous crossing[2]) is a logic puz

en.wikipedia.org

아무튼 이 문제는 $N$범위가 15밖에 안되기 때문에, 배가 위치하는 모든 $O(2^N)$개의 상황을 비트마스킹 등으로 나타낼 수 있다.

이를 정점으로 하고, 배를 한 번 이동시켰을 때 이동 가능한 두 정점 사이를 가중치 있는 간선으로 이어주자.

그러면 일반적인 가중치 그래프에서 출발점과 도착점이 존재하고, 이 사이의 최단거리를 구하는 간단한(?) 문제로 바뀌게 된다.

무조건 배 두 척이 강의 건너편으로 간 다음 한 척이 돌아와야 된다는 관찰을 해낼 수 있었다면, 그래프가 DAG가 되기 때문에 DP로도 풀리게 된다. 이게 훨씬 더 어려운 접근인것 같은데 사람들은 다 이렇게 풀었다. 왤까?

F2. 배 옮기기 (Hard)

https://www.acmicpc.net/problem/28085

28085번: 배 옮기기 (Hard)

www.acmicpc.net

우선 이 논문을 정독한다.

http://page.mi.fu-berlin.de/~rote/Papers/pdf/Crossing+the+bridge+at+night.pdf

그러면 같은 크기의 배도 싣고 갈 수 있는 일반적인 경우에 대한 답을 알 수 있다. 무려 입력을 제외하고 $O(1)$ 해답이 논문에 나와있다.

https://www.acmicpc.net/problem/4381

4381번: Bridge

The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people

www.acmicpc.net

아무튼 저기에서 얻을 수 있는 Insight는 다음과 같다. 정점 번호가 배의 무게이며, 정렬되어 있다고 생각하자.

문제를 $N$개의 정점을 가진 그래프에서 $N-1$개의 간선을 적절히 추가하는 문제로 바꿀 수 있다.
정점 $A$와 정점 $B$를 이은 간선의 가중치는 $\max(A, B)$이고, 우리는 이 가중치의 합을 최소화 해야 한다.
multiple edge가 존재할 수 있지만, 모든 정점은 최소 1의 degree를 가져야 한다.
위를 모두 고려하여 일반적인 문제를 풀 때, 모든 간선은 다음 3가지 중 1가지를 만족한다.
- $i$번 정점과 $i+1$번 정점을 잇는다.
- 1번 정점과 $i$번 정점을 잇는다.
- 1번 정점과 2번 정점을 잇는다.

하지만 우리의 배 옮기기 (Hard)는 같은 크기의 두 배가 한꺼번에 이동할 수 없기 때문에, 여기에서 조금 더 생각을 해 봐야 한다.

간선이 꼭 $N-1$개가 아니어도 된다고 생각해 보자.

그러면 일반적인 그래프에서 Weighted Edge Cover을 구하는 문제로 생각할 수 있다.

그리고 이 문제는..

https://koosaga.com/258

일반 매칭과 응용

유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다. 첫 번째는 문제 그 자체

koosaga.com

koosaga님의 블로그 글을 열심히 읽어서 이해하면 Maximum Weighted Matching 문제로 변환할 수 있음을 알 수 있다.

그리고 이와 관련된 기본(?)문제를 아래에서 풀어볼 수 있다.

https://www.acmicpc.net/problem/15741

15741번: 일반 그래프 최대 가중치 매칭

N개의 정점과 M개의 무방향 간선으로 이루어진 가중치 그래프가 입력으로 주어질 때에, 해당 그래프에서 최대 가중치 매칭의 가중치 합을 출력하는 프로그램을 작성하시오. 그래프 G = (V, E)(|V|=N,

www.acmicpc.net

이건 내가 푼 첫 루비 문제였는데, 혹시 문제 스포일러가 될까 조금 걱정했지만 난이도가 난이도인지라 다행히 아무도 신경쓰지 않은것 같았다.

이쯤해서 이 문제를 진짜로 내도 되는지에 대해 깊이 고민해 보았는데, 어짜피 Open Contest니까 상관없을거라는 팀원들의 응원을 받아 그대로 출제하게 되었다.

난이도에 화가 나신 분들께는 심심한 사과의 말씀을 드립니다.

하지만 이게 또 끝이 아니다. 이대로라면 간선을 $N-1$개보다 작을 수 있기 때문에, 간선을 $N-1$개가 되도록 잘 조정해주는 작업이 필요하다.

단순하게 생각하면 간선 (1, 2)를 부족한만큼 채운 것이 답이라고 생각할 수도 있지만, 쉽게 반례가 나오게 된다. 1번 정점과 다른 정점을 이음으로써 더 좋은 해를 만들 수도 있기 때문이다.

따라서 애초에 Edge Cover를 구할 때 1번 정점을 여러번 사용할 수 있도록 해주는 작업이 필요한데, 이는 1번 정점을 중복해서 여러개 만들어 두는 방법으로 해결할 수 있다.

예를 들어, 1번 정점을 3번 중복해서 간선도 똑같이 이어준 다음 Edge Cover을 구하면, 자동으로 1번 정점이 3번 사용된 최적해를 구하게 된다.

그러면 1번 정점을 중복하여 최대 $N$번까지 추가해서 각각 Edge Cover를 전부 구해준다음, 그 중 최소값을 구하면 된다는 사실을 알 수 있다.

여기에서 끝일 줄 알았는데, 한 가지 예외 사항이 더 있다.

1번 정점과 같은 무게인 배가 이미 많은 경우에는, 이 1번 정점들(?)을 그 다음 무게의 배와 무조건 이어줘야 한다 (이를 2번 정점이라고 하자). 하지만 2번 정점이 적다면 이를 해결해 줄 수 없다. 그렇다면 2번 정점에도 위와 같은 프로세스를 한번 더 돌려주면 된다.

아무튼 종합해보자면, Maximum Weighted Matching이 $O(N^3)$, 그리고 이를 총 $O(N)$번 반복하니 총 $O(N^4)$에 문제를 해결할 수 있다.

그리고 기본 Maximum Weighted Matching의 난이도가 R3이니, 거기에서 1단계 올려서 R2로 난이도를 책정했다.

고수분들의 더 좋은 풀이가 있다면 꼭 알려주세요. 감사합니다.

G. 인경호의 나무

https://www.acmicpc.net/problem/28080

28080번: 인경호의 나무

다음은 인하대학교의 나무 소모임 Cool Tree People (CTP) 회원들 사이에 구전으로 내려오는 전설 "인경호의 나무"에 대한 이야기이다. 인경호의 깊은 바닥에는 노드 $N$개로 이루어진 이진 트리가 있

www.acmicpc.net

문제에서 Binary Search Tree를 설명하고 있다. 자료구조 시간에 수업을 잘 들었다면 BST를 중위 순회한 결과가 오름차순으로 나타내어진다는 사실을 알 수 있다. 그러면 지워진 수들로 인해 이 오름차순의 배열 사이사이에 구멍이 뚫려있을텐데, 구멍의 크기가 $X$이고, 이 사이에 $Y$개의 수가 들어갈 수 있다면 $_YC_X$를 구해서 전부 곱해주면 된다.

H. 직사각형 피자

https://www.acmicpc.net/problem/28081

28081번: 직사각형 피자

첫 번째 줄에 피자의 가로 길이 $W$와 세로 길이 $H$, 부원들이 먹을 수 있는 피자 조각의 최대 크기 $K$가 공백으로 구분되어 주어진다. 두 번째 줄에 가로 방향 커팅의 개수 $N$이 주어진다. 세 번

www.acmicpc.net

피자가 무려 $10^{10}$조각 날 수 있으니 완전 탐색은 불가능하다.

가로 방향이나 세로 방향의 조각 크기를 정렬해 놓고, 이분탐색이나 투 포인터를 이용해 시간복잡도를 줄일 수 있다.

I. 기계오리 연구

https://www.acmicpc.net/problem/28082

28082번: 기계오리 연구

인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언

www.acmicpc.net

Knapsack DP의 응용 문제이다.

$DP_i$를 $i$의 전력량을 만들기 위해 필요한 최소 배터리 개수로 정의하면, $O(NKI)$에 DP테이블을 채울 수 있다.

이 문제는 정해보다 bitset DP로 많이 풀렸는데, DP식을 적당히 짜도 /64 상수 최적화가 가능하기 때문이다.

이를 조금 더 응용해서 bitset으로는 어림도 없고 FFT를 $\log N$번 돌려야 하는 문제를 Hard로 할지 고민했었는데, FFT가 너무 무거워서 여러 번 돌리는 순간 실행시간이 산으로가서 결국 아쉽게 무산되었다.

J. 마왕의 성

https://www.acmicpc.net/problem/28083

28083번: 마왕의 성

세계 정복의 야망을 품은 마왕은 자신의 국가를 만들기로 했다! 하지만 국가를 만들기 전, 영토를 정하거나 성을 세우는 등 해야 할 일이 많다. 영토가 될 수 있는 부지는 $N \times M$크기의 직사

www.acmicpc.net

코드포스 등에서 비슷한 유형의 문제를 접해봤다면 Disjoint Set (Union Find)로 풀리는 매우 전형적인 문제라는 사실을 알 수 있다.

땅을 높이 순으로 정렬해서 낮은 땅부터 미리 계산해 놓으면 더 높은 땅은 낮은 땅에서 계산한 값을 단순히 merge 함으로써 구할 수 있다.

결과

교내대회는 올솔브 방지 1문제를 제외한 9문제가 각각 다른 사람들에 의해 꽤 빨리 풀렸고, 아주 치열한 상위권 싸움을 구경할 수 있었다.

다만 중~하위권의 입장에서는 조금 아쉬운 대회였는데, ABEH(C)를 제외하면 일반적인 학생들은 비빌만한 문제가 부족했기 때문에 평균 솔브 수는 작년보다 적게 나왔다.

다음에 혹시 또 출제하게 된다면 실버~골드 하위 문제들을 더 탄탄하게 만들어 봐야겠다.

오픈컨은 양심 없는 1문제의 존재로 인해 이번에도 올솔브가 나오지 않았다.

올해도 인하대학교 출제진의 승리이다(?)

2023년 5월 22일 현재 solved.ac기준 난이도는 다음과 같다.

마지막으로

재미가 있었다!

'잡담' 카테고리의 다른 글

나쁜 아침입니다. (0)	2023.07.26
2023 KAKAO BLIND RECRUITMENT 1차 코딩테스트 풀이 (10)	2022.09.24
생존신고 (3)	2022.09.02
2022 IUPC (인하대학교 프로그래밍 경진대회) 출제 후기, 해설 (1)	2022.05.24
Code Jam Round 2 2022 (2)	2022.05.15

안즈와 소소한 취미생활