국대교육 일지 - 7/23
오전 셋
임의의 두 정점 쌍에 대해서 두개의 경로만 가지고 있으면 된다. 
쿼리가 없을 경우에는 CHT인데, 쿼리가 있는 것은 왠지 D&C로 될 것 같다. 아직 깊게 생각은 안해봐서 모르겠다.
이분 그래프로 표현한 후, 컴포넌트당 처리한다. 만약 한 컴포넌트라도 functional graph의 형태를 띄지 않으면 0이다.
functional graph에서는 많아야 방향 결정을 2개밖에 못한다. 따라서 두 경우 각각에 대해서 위상정렬을 하고, 적당히 그래프를 그리고 식을 쓰면 계산할 수 있다고 한다. 이것도 잘 모르겠다.
오후 셋
JOISC 17 Day1을 돌았다. 어렵기로 유명했던 셋.
Cultivation
우선 바람의 순서는 상관이 없다.
서풍의 수를 고정시키고 생각할 것인데, 시도할 종류는 많아야 N개이다.
고정시키고 나면, … 귀찮으니까 안쓴다. 정해는 공홈에서 찾을 수 있다. 물론 일본어지만…
Port Facility
여러 종류로 풀 수 있다. 그래프를 만들고 홀수 사이클이 있는지 체크한 후, 컴포넌트 수만큼 2를 곱한 수가 정답이다. 그러나 간선의 수가 너무 많다.
따라서, 한 구간을 잡고 DFS를 하는 것처럼 탐색을 한다. 이것이 가능한 것은 구간을 지우는 것과 구간에 인접한 구간을 찾는 것이 세그트리 등으로 빠르게 가능하기 때문이다.
컴포넌트들을 구하고 나면 가능한지 시도하여 판별하면 된다.
Sparkler
불이 전파된 사람은 구간을 이루고, 불을 빨리 받아서 좋을 것이 없다. 따라서 최대한 천천히 받는 것을 생각한다.
식을 정리하면 두 일차식을 비교하는 것으로 환원되는데, 으아아
공식 풀이를 참조하자.