APIO2012
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명의 닌자가 숨어있다.
그리고 수풀 구간 [si,ei]를 관찰한 관측이 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
- 'Si := i번째 닌자를 매니저로 두었을때 고용되는 닌자들의 집합'이라하자.
- 노드 p 가 부모고 그 자식들이 c1,c2,...ck일때 Sp ⊆ Sc1 ∪ Sc2 ... ∪ Sck} 임은 명백하다.
- 그러므로 다음과 같이 Sp를 구할 수있다: 모든 자식들의 Sci}를 합집합으로 묶고 합집합의 고용비용 총액이 M을 넘으면, 가장 비싼 고용비용을 받는 닌자를 해고하기를 반복한다.
- 노드 x가 Sp를 구할때 포함되지 않았다면 p의 부모 q에서도 포함되지 않을 것이므로, 리프노드부터 순서대로 푼다면 각 노드의 고용상태는 항상 true->false로만 변화한다.
- 이제 노드 p를 중심으로 하는 서브트리 내 고용상태의 노드중 가장 고용비용이 큰 노드 x를 찾는 문제로 바꿀 수 있다.
- 루트가 있는 트리에서 dfs방문 순서대로 번호를 매기면 임의의 서브트리는 [s,e]형태의 구간으로 나오게 됨.
- 따라서 서브 트리내에서 가장 큰 값을 찾는 문제는 구간내에서 가장 큰값을 찾는 문제로 바꿀수 있다.
- 인덱스 트리를 이용하면 O(lg n)시간에 구할 수 있다.
A-2
- 서브트리 내 고용상태이 노드 중 가장 고용비용이 큰 노드 x를 찾는 문제를 다른 방법으로 풀 수 있다.
- 고용 비용에 따라 모든 닌자를 분류했다고 가정하자: ex.) 상위 1/3에 들면 고소득자, 그 다음은 중산층, 저소득자 순.
- 고소득자들의 리스트, 중산층의 리스트, 저소득자의 리스트를 따로 만든다.(각 리스트의 사이즈는 N/3이 될 것이다.)
- 각 노드 i에서 Si 뿐만 아니라 Si에 포함된 고소득자의 수, 중산층의 수, 저소득자의 수를 관리하자.
- 만약 Si의 총 고용비용이 M을 초과할때 Si내에서 가장 많이 버는 계층(예를 들어 고소득자계층)을 바로 알수 있다.
- 가장 많이 버는 계층의 리스트를 전부 살펴보면서, i의 자식인 동시에 가장 월급이 높은 닌자를 찾는다. (dfs방문번호를 이용하면 i의 자식여부를 O(1)에 알 수 있다.)
- 그 닌자를 해고하고 5번부터 다시 반복한다.
- 3개의 그룹 대신 G개의 그룹으로 나누어보자.
- 각 노드i에 대해서 G개의 그룹카운트를 합치는 시간이 필요하므로 O(NG)의 시간.
- 크기가 N/G인 리스트를 최대 N번 탐색할수 있으므로 이때 드는 시간은 O(N*N/G)시간.
- NG + NN/G 를 최소화 하기 위한 G=N^0.5이다. 최종 시간 복잡도는 O(N^1.5)
B
- 닌자가 관측되지 않은 지점을 지웠을때 남은 수풀수가 K라면 명백하다.
- 닌자가 관측된 구간중 관측안된 구간을 전부 지웠을때 내부의 수풀 수가 1개라면 명백하다.
- 위의 2개의 케이스를 먼저 처리하고, 남은 구간들을 그리디하게 풀었을때 구한 답이 정확하게 K라면, 그리디로 나온 구간중에 정답이 존재 할 수있다.
- 그리디하게 나온 구간이 단 한 개의 수풀을 포함하고 있다면, 그 수풀을 제거함에 따라 그리디 답이 1증가 할수 있다. 그러면 K를 초과하게 되므로 그 수풀이 답이 되게 된다. 각 수풀을 지우고 다시 그리디를 풀어보는건 N이 크기 때문에 오래걸린다. 미리 뒤에서부터 푸는 그리디를 선처리 해두고, 그 수풀을 지나는 모든 수풀들이 뒤에서 부터 푸는 그리디에 포함되는지 체크하면 된다.
- 주의할 점: 닌자를 관측한 구간의 맨앞 또는 맨뒤가 관측못한 구간과 겹치면 그만큼 축소시켜줘야 그리디가 올바르게 나온다.
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는 가로로 그어진 구간 또는 세로로 그어진 구간이 된다.
- 가로 구간들을 정렬해서 앞의 구간에 길이를 덧붙여서 면적을 구한다.
- 세로 구간들을 정렬해서 똑같이하되 그 구간내에 그어진 가로선의 갯수만큼 제외한다.(인덱스트리 이용)