오전 셋

2016, 17서울대학교 셋중 몇개를 풀었다.

16 K. 검역소
파라메트릭으로 그리디하게 하면 O(Nlog^2N)에 된다.

16 L. 직사각형의 개수
분할 정복 혹은 비트마스킹으로 할 수 있다고 한다. 분할정복을 하면 O(K^2(N^2+M^2))이다.

17 Div 1. G. 타일 뒤집기 (Hard)
이웃한 4개의 칸에 검은 칸이 짝수개 있으면 된다. 그래서 45도 돌려서 축에 써놓고 하면 으레 있는 그것처럼 된다.

오후 셋

저번에 했던 APC01 몇개를 돌았다.

E. Antennas on the tree
어떤 한 점을 잡았을 때를 생각해보면, 모든 서브트리에 대해서 DP값을 가지고 있으면 된다는 것을 알 수 있다. 이를 위해서 모든 트리의 지름을 구하는 것처럼 트리의 크기순으로 DP를 채우면 된다. O(deg^2)이 되지 않도록 조심해야 한다.

G. Colorful Doors
이리저리 경우를 나누면 된다. 전부 1일때, N이 짝수일때, 홀수일때, 전부 1이 아닐 때, 짝수일 때, 등등. 하면 된다.
IOI08 Teloporters와 세팅이 비슷한 문제인데, 이렇게 생긴 그래프를 분석해보면, 모든 점은 outdegree와 indegree가 1이다. 그래서 그래프를 분리하면 disjoint한 사이클들의 집합으로 구성되며, 점의 개수로부터 사이클의 개수의 기우성을 얻을 수 있다.

I. Simple APSP Problem
그리드를 압축해서 생각하면, O(N^4)에 할수 있다. 이정도는 풀만해야 할 것 같은데. 흠