JOI Spring Camp 2019 Day 1 Solutions

1. Examinations

학생별로 (S, T)가 입력으로 주어지는데, 이것을 쿼리와의 일관성을 위해(S, T, S+T)의 tuple로 해석하자. 쿼리 (X, Y, Z)가 들어오면, S>=X&&T>=Y&&S+T>=Z인 쌍의 개수를 출력하는 것이 문제이므로, 둘다 내림차순으로 적절히 정렬한 다음 2d update와 query로 문제를 풀어주자. 쿼리에 대한 분할정복+펜윅 스위핑을 하면 O((N+Q)log^2(N+Q))에 AC.

 

2. Naan

일단 각 사람별로 각각 한 조각에 sum/N씩 있도록 처음부터 잘라준다. 사람 i에 대한 j번째 조각의 끝점을 A[i][j]라 하겠다. A[i][j]는 유리수. (유리수끼리의 비교함수를 작성할때 overflow를 조심하도록 하자...) 이제 greedy하게 조각을 처음부터 뽑아주면 된다. j번째 조각을 뽑을때에는 아직 조각이 배정되지 않은 사람들 중 A[i][j]가 최소인 사람 i에게 그 조각을 주고, A[i][j]위치에서 잘라주면 된다. 증명으로는 바로 전 배정된 사람을 k라 하면, A[k][j-1]<=A[i][j-1]이고, A[i][j]-A[i][j-1]=sum[i]/N<=A[i][j]-A[k][j-1]이기 때문에 항상 i번 사람은 sum[i]/N보다 크거나 같은 조각을 배정받게 된다. 그림을 그려보면 매우 쉽게 생각할 수 있는 그리디인 것 같다. O(NL)에 AC.

 

3. Meetings

Query(a, b, c)를 호출했을 때 리턴되는 값에 대해 고민해보자. a, b, c가 같은 직선 위에 있지 않으면, 리턴값 d에 대해 path(a, d)∩path(b, d)∩path(c, d)=0인 d고, d는 유일하다. 같은 직선 위에 있으면 a, b, c중 중간에 끼어있는 정점을 리턴할 것이다. 그렇다면, 임의로 x, y를 고정시킨 뒤 다른 모든 정점들에 대해 쿼리를 호출하고, Query(x, y, i)==i면 i는 x와 y를 잇는 path 위의 정점일 것이고, Query(x, y, i)=j이면 i는 j번 정점에 달려있는 subtree의 정점이라는 걸 알 수 있다. 위의 정보를 가지고 path위의 정점들을 x에서 y로 가는 순서대로 정렬한 다음, path위의 있는 순서대로 grader에 호출한 뒤 각 subtree에 대해 재귀적으로 같은 문제를 풀어나가면 된다. 정렬하는 함수가 이쁜데, i와 j를 비교하는 comp 함수에 return Query(x, i, j)==i;를 해주면 된다. 이러면 29점이 나오고, 만점은 x와 y를 랜덤 지정해주면 나온다고 하는데... 이게 왜되는지 아직 잘 모르겠다. maxdegree가 18이하라는 조건때문에 그런 것 같은데 자세한 증명은 나중으로 미루도록 하겠다.

 

풀이를 떠올릴 때 3번처럼 Random도 가끔은 고려해주도록 하자.