2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest

2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest

A - 모비스

단순 구현

00:01 AC

 

E - 중력 큐

정말 정직하게 구현해주면 된다.

다만 rotate로 인하여 양방향에서 제거가 일어나기 때문에 queue 대신 deque을 사용해야 한다.

00:13 WA

pop 이후 연쇄적인 제거가 일어날 수 있음에 유의해야 한다.

00:15 AC

 

B - 스파이

정해는 완전 탐색인데 나는 dp로 풀이하였다.

다음과 같은 점화식을 세울 수 있다.

dp[i][j][k] = i일차에 {"수족관", "시청", "학교"}[j]에서 임무를 수행하였을 때 기여도를 k만큼 얻을 수 있는 임무 수행 방법의 수

00:22 AC

 

C - 멀티탭 충분하다

정삼각형 형태로 쌓아 올리면 되는데 항상 최대 3개의 멀티탭만 보이도록 쌓을 수 있다.

배열 A를 내림차순으로 정렬하였을 때 답은 (A[p1] + A[p2] + A[p3] - 3)이 된다.

zero-based indexing 기준으로 인덱스는 다음과 같다.

• p1 = 0;
• p2 = (N + 2) / 3;
• p3 = 2 * p2 - (N % 3 == 1);

00:29 AC

 

H - 직사각형 피자

이분 탐색

00:53 AC

 

I - 기계오리 연구

bitset dp로 풀이할 수 있는데 점화식은 다음과 같다.

dp[i][j] = i개의 배터리를 장착하였을 때 전력량을 j로 만들 수 있다면 1, 그렇지 않다면 0

00:57 AC

 

정해는 일반적인 dp인데 점화식은 다음과 같다.

dp[i] = 전력량을 i로 만들기 위한 배터리의 최소 개수

발상은 bitset dp가 더 간단하다.

 

J - 마왕의 성

높이가 낮은 땅부터 Union-Find로 적절히 관리하면 된다.

01:07 AC

 

G - 인경호의 나무

inorder traversal 이후 조합 공식으로 적절히 세주면 된다.

01:16 AC

 

F - 배 옮기기

bitmask dp

01:38 AC

정해는 dijkstra라고 한다.

 

B2 - 스파이 (Hard)

기존 dp 점화식을 행렬 거듭제곱으로 빠르게 계산해주면 된다.

다만 기존 점화식이 3차원이라서 행렬로 변환하기가 쉽지 않다.

점화식이 N차원인 경우 적절히 2차원으로 변환한 후 행렬로 변환하면 된다.

01:51 AC

 

D - 사탕 팔찌

우선 N = K이면 답이 존재하지 않는다.

각각의 사탕 묶음을 하나의 정점으로 생각하면 hamiltonian cycle을 구하는 문제가 된다.

하지만 이는 다항 시간에 구하기 어렵다.

 

생각을 조금 바꾸어서 각각의 사탕 묶음을 하나의 간선으로 생각해보자.

예를 들어 사탕 묶음 ABC는 정점 AB에서 정점 BC로 가는 간선으로 볼 수 있다.

사탕 묶음 ABCD의 경우 정점 ABC에서 정점 BCD로 가는 간선으로 보면 된다.

이제 기존 문제를 eulerian cycle을 구하는 문제로 변형할 수 있다.

02:42 AC

 

F2 - 배 옮기기 (Hard) (not solved)

general matching 문제로 모델링이 가능한데 현재 루비 2가 찍혀 있다.

처음에는 기분이 나빴는데 koosaga님 템플릿 복붙하니 레이팅 낭낭하게 빨 수 있었다.

오히려 감사합니다.

 

끝

끝