APIO 2012

http://www.ioi-jp.org/apio2012/

문제요약

A.
n<=100,000 이 주어지고 크기가 n인 닌자들로 이루어진 rooted tree가 주어진다.(root=1)
각 닌자의 리더십점수 L[i]와 고용비용 C[i], 부모 P[i]가 주어진다.
임의의 닌자를 매니저로 정한다. 매니저의 직/간접적인 자식들(후손)은 프로젝트에 투입될 수 있다.
(매니저는 프로젝트에 참가하든 하지않든 상관없다.)
이때 프로젝트의 투입된 인원들의 총 고용비용이 M(<=1,000,000,000)을 넘지않게 하면서
[매니저의 리더십 점수] * [투입된 인원수] 를 최대화하라.

B.
n<=100,000 개의 수풀속에 k<=100,0000명의 닌자가 숨어있다.
그리고 수풀 구간 [s_i,e_i]를 관찰한 관측이 m<=100,000개 있다.
이때 관측은 '최소한 닌자가 한 명 이상 존재하는지'만을 판단할 수 있다.
n k m이 주어지고 관측이 m개 주어질 때, 닌자가 반드시 존재하리라 생각되는 수풀의 위치를 출력하라.

C.
n<=100,000 명의 닌자가 1<=W,H<=1,000,000,000 위의 격자상에 존재한다.
각 닌자는 고유의 (x,y)좌표 상에서 '상하좌우'중 한 방향으로 kunai를 던진다.
모든 닌자가 던진 kunai는 같은 속도로 등속운동을 한다.
또한 kunai가 서로 교차하거나, 한 격자에 동시에 모이는 순간 모든 kunai는 사라진다.
이때 모든 kunai가 지나간 자취의 면적을 구하라.

##풀이
A.
1. 'S_i := i번째 닌자를 매니저로 두었을때 고용되는 닌자들의 집합'이라하자.
1. 노드 p 가 부모고 그 자식들이 c1,c2,...ck일때 S_p ⊆ S_c1 ∪ S_c2 ... ∪ S_ck 임은 명백하다.
1. 그러므로 다음과 같이 S_p를 구할 수있다: 모든 자식들의 S_ci를 합집합으로 묶고 합집합의 고용비용 총액이 M을 넘으면, 가장 비싼 고용비용을 받는 닌자를 해고하기를 반복한다.
1. 노드 x가 S_p를 구할때 포함되지 않았다면 p의 부모 q에서도 포함되지 않을 것이므로, 리프노드부터 순서대로 푼다면 각 노드의 고용상태는 항상 true->false로만 변화한다.
1. 이제 노드 p를 중심으로 하는 서브트리 내 고용상태의 노드중 가장 고용비용이 큰 노드 x를 찾는 문제로 바꿀 수 있다.
1. 루트가 있는 트리에서 dfs방문 순서대로 번호를 매기면 임의의 서브트리는 [s,e]형태의 구간으로 나오게 됨.
1. 따라서 서브 트리내에서 가장 큰 값을 찾는 문제는 구간내에서 가장 큰값을 찾는 문제로 바꿀수 있다.
1. 인덱스 트리를 이용하면 O(lg n)시간에 구할 수 있다.

A-2.
1. 서브트리 내 고용상태이 노드 중 가장 고용비용이 큰 노드 x를 찾는 문제를 다른 방법으로 풀 수 있다.
1. 고용 비용에 따라 모든 닌자를 분류했다고 가정하자: ex.) 상위 1/3에 들면 고소득자, 그 다음은 중산층, 저소득자 순.
1. 고소득자들의 리스트, 중산층의 리스트, 저소득자의 리스트를 따로 만든다.(각 리스트의 사이즈는 N/3이 될 것이다.)
1. 각 노드 i에서 S_i 뿐만 아니라 S_i에 포함된 고소득자의 수, 중산층의 수, 저소득자의 수를 관리하자.
1. 만약 S_i의 총 고용비용이 M을 초과할때 S_i내에서 가장 많이 버는 계층(예를 들어 고소득자계층)을 바로 알수 있다.
1. 가장 많이 버는 계층의 리스트를 전부 살펴보면서, i의 자식인 동시에 가장 월급이 높은 닌자를 찾는다. (dfs방문번호를 이용하면 i의 자식여부를 O(1)에 알 수 있다.)
1. 그 닌자를 해고하고 5번부터 다시 반복한다.
1. 3개의 그룹 대신 G개의 그룹으로 나누어보자.
1. 각 노드i에 대해서 G개의 그룹카운트를 합치는 시간이 필요하므로 O(NG)의 시간.
1. 크기가 N/G인 리스트를 최대 N번 탐색할수 있으므로 이때 드는 시간은 O(N*N/G)시간.
1. NG + NN/G 를 최소화 하기 위한 G=N^0.5이다. 최종 시간 복잡도는 O(N^1.5)

B.
1. 닌자가 관측되지 않은 지점을 지웠을때 남은 수풀수가 K라면 명백하다.
1. 닌자가 관측된 구간중 관측안된 구간을 전부 지웠을때 내부의 수풀 수가 1개라면 명백하다.
1. 위의 2개의 케이스를 먼저 처리하고, 남은 구간들을 그리디하게 풀었을때 구한 답이 정확하게 K라면, 그리디로 나온 구간중에 정답이 존재 할 수있다.
1. 그리디하게 나온 구간이 단 한 개의 수풀을 포함하고 있다면, 그 수풀을 제거함에 따라 그리디 답이 1증가 할수 있다. 그러면 K를 초과하게 되므로 그 수풀이 답이 되게 된다. 각 수풀을 지우고 다시 그리디를 풀어보는건 N이 크기 때문에 오래걸린다. 미리 뒤에서부터 푸는 그리디를 선처리 해두고, 그 수풀을 지나는 모든 수풀들이 뒤에서 부터 푸는 그리디에 포함되는지 체크하면 된다.
1. 주의할 점: 닌자를 관측한 구간의 맨앞 또는 맨뒤가 관측못한 구간과 겹치면 그만큼 축소시켜줘야 그리디가 올바르게 나온다.

C.

• 문제1 : 각 kunai의 life time구하기
• 문제를 1차원으로 축소해서 고려해보자. 여기서 모든 kunai들은 오른쪽(R) 또는 왼쪽(L)으로만 움직인다.
• x값 순서대로 kunai 발사방향이 RRRLLLLRRRLLL... 이런식으로 되어있다면 가장 먼저 충돌할 곳은 RL이 인접한 곳중 한 곳이 될것이다.
• 그러므로 모든 RL인접에 대해서 충돌시간을 계산해서 PQ에 넣고, 가장 짧은 RL충돌을 구해서 둘을 삭제한다. 그리고 삭제로 인해 새로운 RL인접이 생기면 PQ에 추가하기를 반복한다.
• 이 때의 시간복잡도는 O(n lg n)이 된다.
• 2차원이 되어도 문제는 크게 다르지않다. 6개의 충돌을 각각 고려해서 리스트로 관리해주면된다. (RL,DU,DL,DR,UL,UR)
• 문제2: 흔적의 면적 구하기
• 각 kunai는 가로로 그어진 구간 또는 세로로 그어진 구간이 된다.
• 가로 구간들을 정렬해서 앞의 구간에 길이를 덧붙여서 면적을 구한다.
• 세로 구간들을 정렬해서 똑같이하되 그 구간내에 그어진 가로선의 갯수만큼 제외한다.(인덱스트리 이용)