국대교육 일지 - 7/24 | Diuven’s Blog

오전 셋

KOI 중등부를 돌았다. 2시간 반정도, 4문제.

한 셀에서 바깥으로 가는 경로들 중 경로상의 모든 구멍의 높이의 최대값의 최소값이 그 셀의 높이이다. 적당히 다익스트라하면 된다.

최저점 기준으로 소팅, $O(N^2)$ DP를 채우는데 한 점을 잡고 다른 점을 다 소팅하고 채우면 $O(N^2logN)$ 에 된다.

오후 셋

JOISC 2017 Day 3+a를 돌았다. 문제 너무 어렵다.

의미있는 간선은 모두 $O(N)$ 개이고, 이걸로 쿼리를 처리하면 $O(NQ)$ 까지는 된다.

그런데 이 그래프을 그리고 듀얼을 그려보면 트리이고, 따라서 LCA를 적당히 구하고 올라가면서 계산하면 된다고 한다.

각 노드에서 갈 수 있는 구간을 구하는데, 스택에 넣으면서 하면 생각보다 빠르게 가능하다. $O(NlogN)$ 에 된다고 한다.

트리를 만들면서 한다고 생각해 보면, 한 정점을 트리에 붙이는데 대략 $O(logN)$ 정도가 걸린다. (한 정점을 잡고, 그 정점이 트리와 연결된 점을 찾고, 그 경로 상의 모든 점을 넣는 것이 각 정점당 $O(logN)$ 에 된다.)

그래프에서도 마찬가지로 하면 되는데, 이때는 그래프와 연결되는 정점을 찾고, 그 정점을 없앤 후 생기는 컴포넌트당 재귀적으로 다시 해주면 된다.

업솔빙 안하련다. 지금은 그런거보다 생각하는 방법을 정립하는 것이 더 중요할 것 같아서, 안 풀어본 문제를 푸는 것이 좋을 것 같다.

일단 오늘은 졸리니까 좀 자고.