[ICPC 본선 대비 뇌셋] Day 16

이번에 레프와 같이 다이아를 다섯개쯤 쌓아두고 네시간동안 흙찡구놀이를 했다. 물론 처참하게 발렸다.

백준 10014번 Travleling Saga Problem www.acmicpc.net/problem/10014

10014번: Traveling Saga Problem

나답게 그리디스럽게 접근하다가 레프가 걍 센트로이드로 풀면 된다고 했고(트쿼 4와 유사한가보다) 그쪽으로 풀이를 짰다. 풀이 자체는 간단하다만 세시간동안 메모리초과와 시간초과를 사이좋게 나눠 받다가 사망했다.

[풀이] 세상에, Saga가 사과라는걸 방금 봤다. 사과나무를 점프하면서 돌건데, 정점에서 거리가 제일 먼 점으로 가면 된다. centroid decomposition을 해놓고, 분해된 각 서브트리 노드에서 서브트리의 루트까지의 거리를 priority-queue로 저장한다.(노드를 지우면 길이가 1씩 줄어든다는 성질을 이용해 list로 저장할 수 있다. 이렇게 하면 시간초과가 안뜨려나)

[쿼리 1] 가장 먼 점 찾기

현재 점에 포함된 가장 작은 서브트리로부터 최대 서브트리까지 올라가면서 각 루트에서 가장 먼 점을 pq.top()으로 찾는다. 다만 주의해야할 점은, 최댓값이 같은 서브트리의 같은 부분에 있으면 안되는데, 이를 위해서 두번째 원소까지 찾아주는 번거로움을 겪어야한다. pop두번 하고 다시 push하는 식으로 구현하면 된다. 물론 TLE코드 기준ㅋㅋ

pq코드 기준 O(Nlg^2(N))

list로 바꾸면, 각 서브트리에서 노드까지 길이는 서브트리의 크기보다 작거나 같으므로 O(NlgN)만에 할 수 있다. 통과하려면 이렇게 짜야하는듯... 자료구조 문제는 언제나 (심지어 코딩을 안하고 옆에서 보고만 있어도)짜증난다.

 

그 다음은 뭔가 좀 많이 어려워서 생각의 고비가 많았던 "친구" 문제이다. IOI 2014년 문제였다.

백준 10075번 www.acmicpc.net/problem/10075

10075번: 친구

하...ㅋㅋ 풀어서 다행인데, 코드 길이를 풀기 전에 봤으면 더 빨리 떠올렸을 것 같기도 하고.. 모르겠다.

결론적으로는 최대 가중치 합 독립집합을 찾는 문제이다.

그래프의 조건이 좀 많이 특이하므로, 그래프의 특징을 찾아내야 한다. 하지만 그에 앞서, 다음과 같은 생각은 쉽게 할 수 있다.

[관찰 1] 쿼리 0만 있을경우, 즉 그래프가 트리일 경우에는 Tree DP를 이용해서 풀 수 있다.

이제 당연히 N-1에서 0으로 가는 DP를 변형할 생각을 해야한다. 이제 그래프의 특징을 찾아내야 한다.

관찰 1과 비슷한 방법으로 트리 DP의 형태로 문제를 해결하기 위해서는, 일단 그래프의 개형이 tree에서 크게 벗어나면 안된다. 따라서 다음과 같은 생각을 할 수 있다.

[관찰 2] 2번과 3번의 쿼리를 받은 i번째 친구는 호스트 위에 얹어놓는다.

풀이에 직접적으로 쓰이진 않지만, 나는 이렇게 그린 그림에서 풀이를 생각하는 것이 더 수월했다.

이제 2번(빨강색)과 3번(파란색) 쿼리를 받은 친구들은 그 검은색 베이스의 Neighbor에 있는 친구들과만 사귈 수 있다. 따라서 2, 3번 쿼리의 특징을 살피기 위해서 두개의 검은색 노드를 베이스로하는 이분그래프를 생각해볼만 하다.

이때, 이 이분그래프는 완전 이분그래프가 된다.

따라서 한쪽 검은색 노드를 베이스로하는 친구가 선택되었다면, 나머지 노드를 베이스로 하는 친구들은 한명도 선택될 수 없다.

[관찰 3] 2, 3번 쿼리로만 이루어진 그래프에서, i가 쿼리 3으로 호출되었다면, 연결된 자식 노드들이 하나 이상 선택되었을 때 i는 선택될 수 없다. 쿼리 2로 호출된다면 그러한 조건 없이 선택 될 수 있다.

이제 이러한 관찰들을 바탕으로 DP를 생각 할 수 있다.

B[i].va = (i ~ n-1까지의 노드를 선택했을 때 가질 수 있는 최댓값)

B[i].vb = (노드 i의 2번과 3번 쿼리들로만 연결된 i 이상의 노드들이 모두 선택되지 않은 최댓값)

DP 배열의 의미만 생각했다면, 쿼리들에 대해서 DP table을 갱신하는 것은 어렵지 않다.

쿼리 1:

B[i].va = max(B[i].va+B[p].vb, B[i].vb+B[p].va)

B[i].vb = B[p].vb+B[i].va

쿼리 2:

B[i].va = B[p].va+B[i].va

B[i].vb = B[p].vb+B[i].vb

쿼리 3:

B[i].va = max(B[p].va+B[i].vb, B[i].va+B[p].vb)

B[i].vb = B[p].vb+B[i].vb

코드는 짧지만 어려운 문제였다..