제1회 보라매컵 본선 Open Contest
제1회 보라매컵 본선
www.acmicpc.net
서론
설 연휴랑 겹쳐서 업솔빙하였다.
A - 장기자랑
먼저 배열 A를 정렬하자.
N번 병사, 1번 병사, (N - 1)번 병사, 2번 병사, ... 순으로 공연하면 항상 최적이 된다.
엄밀한 증명은 까다롭지만 코포식 그리디 느낌으로 접근하면 쉽게 풀이할 수 있다.
B - 영내순환버스
식을 세워서 잘 계산하면 된다.
C - 조사전달
많은 인원이 필요한 사역에 최대한 적은 병사가 차출되도록 하면 된다.
배열 A와 B를 정렬한 후 그리디하게 매칭시켜주면 된다.
이 문제 역시 코포식 그리디 느낌으로 접근하면 된다.
D - 이기적인 목봉 체조 (Easy)
다음과 같은 점화식을 세울 수 있다.
dp[i][j] = [1 .. j]번 훈련병을 i개의 그룹으로 편성할 때 들 수 있는 목봉 무게의 합의 최댓값
구체적으로는 다음과 같이 계산할 수 있다.
A[i][j] = [i .. j]번 훈련병을 그룹으로 편성할 때 들 수 있는 목봉 무게
dp[i][j] = max(dp[i - 1][k] + A[k + 1][j]);
E - 운전병의 딜레마
이분 탐색 + dijkstra
F - 체육 대회
완전 탐색을 잘 하면 된다.
다음과 같은 배열 C를 정의할 수 있다.
C[i][j][k][l] = 팀 i가 x번째 종목에서 실력의 합이 {j, k, l}[x] 이상이 되는 병사 배치가 존재하면 1 그렇지 않으면 0
G - MVP 투표
functional graph 문제인데 이러한 문제는 구현이 상당히 까다롭다.
functional graph에서는 모든 연결 요소마다 하나의 사이클이 생성된다.
크기가 홀수인 사이클과 짝수인 사이클을 각각 홀수 사이클과 짝수 사이클이라고 하자.
홀수 사이클에는 반드시 거짓말쟁이가 존재해야 하며 짝수 사이클에는 거짓말쟁이가 존재할 수 없다.
위의 정보를 바탕으로 case work를 해보자.
(i) 홀수 사이클이 존재하지 않는 경우
거짓말쟁이는 사이클에 속하지 않는다.
(ii) 홀수 사이클이 1개 존재하는 경우
거짓말쟁이는 홀수 사이클에 속한다.
(iii) 홀수 사이클이 N개 존재하는 경우
이 경우 거짓말쟁이가 N명 존재해야 하므로 답은 -1이 된다.
각 연결 요소에 대하여 dfs를 돌리면 사이클을 찾을 수 있다.
이제 모든 후보 병사에 대하여 최소 인원수 조건을 만족하는지 검사해주면 된다.
dfs 과정에서 적절히 전처리를 해준다면 상수 시간에 검사가 가능하다.
한 팀의 인원만 M명 이상이면 되므로 최대한 한 팀에 몰면 된다.
더러운 구현을 요구하는 functional grpah 문제는 방출입니다.
H - 이기적인 목봉 체조 (Hard)
D번에서 N 제한이 커졌다.
뭔가 dnc opt가 될 것 같이 생겼는데 안 된다.
N 제한이 커졌으므로 기존의 배열 A를 그대로 사용할 수 없다.
다음과 같이 배열 A를 재정의하자.
A[i] = [i .. x]번 훈련병을 그룹으로 편성할 때 들 수 있는 목봉 무게
x가 증가함에 따라 배열 A도 적절히 업데이트해야 한다.
dp 배열은 다음과 같이 계산된다.
dp[i][j] = max(dp[i - 1][k] + A[k + 1]);
구체적으로 살펴보면 다음 집합에서 최댓값을 찾는 것이다.
{dp[i - 1][0] + A[1], dp[i - 1][1] + A[2], dp[i - 1][2] + A[3], ..., dp[i - 1][j - 1] + A[j]}
다음과 같은 배열 maxh를 정의하자.
maxh[i] = [i .. x]번 훈련병의 키 중 최댓값
배열 A는 다음과 같이 업데이트된다.
if maxh[i] == H[j] then
A[i] += S[j];
elif maxh[i] < H[j] then
A[i] = S[j];
u < v일 때 maxh[u] >= maxh[v]가 성립함에 주목하자.
maxh의 대소 관계에 따라 배열 A는 다음과 같이 업데이트된다.
if maxh[u] == maxh[v] then
if maxh[v] <= H[x + 1] then
// update A[u] and A[v]
else
if maxh[u] <= H[x + 1] then
// update A[u] and A[v]
elif maxh[v] <= H[x + 1] then
// update A[v]
maxh[u] == maxh[v]인 경우에는 두 값이 동시에 업데이트되므로 두 값을 하나로 합쳐서 관리할 수 있다.
구체적으로는 (dp[i - 1][u - 1] + A[u])와 (dp[i - 1][v - 1] + A[v]) 중 최댓값만 관리하면 된다.
주의할 점이 있는데 maxh[v] < H[x + 1]인 경우 A[u]와 A[v]는 모두 S[x + 1]로 초기화된다.
이때 (dp[i - 1][u - 1] + A[u])와 (dp[i - 1][v - 1] + A[v])의 대소 관계가 뒤바뀔 수 있다.
따라서 dp 배열의 최댓값도 별도로 관리해야 한다.
maxh[u] > maxh[v]에서 maxh[u] == maxh[v]가 되는 경우도 유사하게 처리해주면 된다.
핵심적인 성질을 정리하면 다음과 같다.
- u < v일 때 maxh[u] >= maxh[v]가 성립한다.
- maxh[u] == maxh[v]인 경우에는 두 값을 하나로 합쳐서 관리할 수 있다.
여기에 가장 적합한 자료 구조가 있는데 바로 stack이다.
구체적인 연산 과정은 약간 복잡하다.
다음과 같은 구조체 rec를 정의하자.
struct rec {
ll a, b, c;
};
각 변수는 다음을 의미한다.
- a = 현재 묶음의 maxh
- b = (maxh[x] == a)를 만족하는 x에 대하여 max(dp[i - 1][x - 1] + A[x])
- c = (maxh[x] == a)를 만족하는 x에 대하여 max(dp[i - 1][x - 1])
추가적으로 stack에 들어 있는 모든 묶음의 b를 저장하는 multiset을 관리하자.
dp[i][j]의 값은 multiset의 원소 중 최댓값이 된다.
조금만 노력하면 multiset 없이 풀이할 수도 있다.
구조체 rec에 변수 d를 추가하는데 d는 현재 묶음과 이전의 모든 묶음에 대하여 max(b)를 관리하도록 하자.
dp[i][j]의 값은 stack에서 가장 위에 있는 묶음의 d가 되며 이는 앞서 구한 값과 동일하다.
끝
끝