국가대표 멘토링 교육 3주차 후기

JOISC 2016/2017 Day 3을 돌았다. 그런데 A번인 Long Distance Coach는 2차 선발고사 준비를 할 때 시도를 하고 풀이를 들은 적이 있어서, 풀이가 가물가물하긴 하지만 정상적인 문제풀이 과정보단 잊어먹은 풀이를 떠올리기 위한 시도가 될 거 같아서 JOISC 2015/2016 Day2 1번 Employment로 교체했다.

 

A. Employment

 

갱신 쿼리가 없다고 생각하고 평가치가 높은 후보자부터 채용하면서 독립집합의 개수의 변화를 관찰해보자. 양쪽에 채용된 후보자가 없으면 개수가 1개 늘고, 한쪽은 채용되었고 한쪽은 안 되어있으면 개수가 변화하지 않고, 양쪽 다 채용되어있으면 개수가 1개 줄어든다. 이 변화가 단지 양옆 후보자의 채용여부(양옆 후보자의 평가치)에만 영향을 받는다는 사실에 주목하자.

일단 평가치 순서대로 좌표압축을 해서 독립집합 개수 변화들을 모두 집어넣고 세그먼트 트리에서 합을 구하면 어떤 평가치까지 채용했을 때 독립집합 개수를 구할 수 있다. 그리고 갱신 쿼리는, c 위치를 바꾸면 독립집합 개수변화치가 바뀌는 건 c-1,c,c+1뿐이므로 여기에 대해서만 다시 값을 계산하고 세그먼트 트리를 갱신해준다. 이때 c 위치의 변화치 값은 평가치 값이 바뀌니까 다른 곳에 갱신해줘야 한다. 이러면 O(NlogN)에 문제를 풀 수 있다.

 

B. Long Mansion

 

Subtask 1,2는 dp[l][r]=왼쪽으로 l까지, 오른쪽으로 r까지 도달하였을 때 최종적으로 왼쪽으로 어디까지, 오른쪽으로 어디까지 도달할 수 있을까? 로 정의하여 풀면 풀릴듯하다.

Subtask 3은 시작점 N개에 대해서 각각 봐준다. 현재 가지고 있는 열쇠로 도달할 수 없는 가장 가까운 점을 빠르게 구해주면 한 번 계산마다 보유한 열쇠 개수가 하나 이상 늘어나거나 아예 더이상 나아갈 수 없게 되니까 문제가 풀릴듯하다.

풀 태스크는 잘 모르겠다.

 

C. Natural Park

 

Subtask 1은 모든 NC2가지의 가능한 간선 경우의 수에 대해, a b 말고 다 이동불가로 설정하고 a b 사이를 이동할 수 있는지 확인하면 a b 사이의 간선 존재 여부를 확인할 수 있고 서브태스크가 풀린다.

Subtaks 2는 문제를 1~N-2의 수를 정렬하는 것으로 환원할 수 있다. a와 b의 대소관계는 a만 이동불가로 지정하고 0에서 b까지 갈 수 있다면 b<a이고 갈 수 없다면 a<b이다. O(NlogN)번만 대소관계를 비교해도 되므로 정렬 알고리즘을 사용하여 풀 수 있다.

Subtask 3 : 0번 정점을 루트로 하는 트리를 생각하자. 8N번의 함수 호출만으로 각각의 높이에 존재하는 정점들의 목록을 얻을 수 있다. 이제 정점들에 대해서 부모를 찾아주기만 하면 그래프를 복구할 수 있다. 높이 i에 있는 정점 v에 대해, 높이가 i-2 이하인 정점은 모두 이동가능, 높이가 i-1인 정점은 일부만 이동가능, v는 이동가능, 나머지는 이동불가능으로 설정하고 0에서 v로 이동가능한지 함수를 호출하면 높이가 i-1인 정점 중 이동 가능하게 설정한 일부 중에 v의 부모가 있는지 확인할 수 있다. 이 방식으로 이분탐색을 하면 정점당 O(logN)의 함수호출로 정점의 부모를 찾을 수 있다.

그 이후의 서브태스크는 차수 조건을 써야할듯한데 어떻게 사용할지 잘 모르겠다. 트리문제라는 공통점과 트리의 구조에 특별한 제한을 넣었다는 점에서 그 다음 Day의 City가 떠오르는데 그 문제도 되게 어려웠어서 이 문제도 되게 어려울 거 같다는 생각이 든다.