[ICPC 본선 대비 뇌셋] Day 20

이제 이 제목의 글도 내일이면 끝이다.

백준 10167번 금광 www.acmicpc.net/problem/10167

10167번: 금광

오늘은 좀 쉬어가는 느낌으로 금광을 짰다. 풀이는 대충 창기한테 들었고, 구현을 해봤는데 시간이 좀 느리게 나왔다. 다른 여러 블로그에 풀이가 많으니 그걸 보는게 좋을 것 같다. 물론 이런 문제가 나오면 이메이미가 밀겠지만 어떻게 생겨먹은 세그인지는 알고싶어서..

 

오늘 좀 놀았는데 그러기엔 죄책감이 들어서 재작년에서 어려웠던 문제들을 좀 보고 생각해봤다. 

백준 16364번 Simple polygon www.acmicpc.net/problem/16364

16364번: Simple Polygon

풀이는 무척 간단하나... 구현이 매우 매우 헬일것으로 예상한다. x점을 x축에 붙어있는점, 윗점을 x점과 연결된 윗점이라고 하자.

[관찰] 일단 양 끝의 윗점은 서로 연결되어야하고, 그 안에 모든 다른 윗점들이 있어야한다. 그리고 인접한 두 쌍의 점들끼리만(총 네가지) 붙을 수 있다. 따라서 DP를 돌리면 된다.

고려해야할 것은 두 직선이 만나면 안된다는 것인데, 새로 연결하는 선분을 고려할때는 그 이전 선분들이 모두 왼쪽에 있 고려하면 됨을 쉽게 보일 수 있다. 따라서 그것을 해주면 되는데..... 이게 헬이다. rotating calipers로 풀릴 것 같으나 토악질이 나와서 더 생각은 안해봤다.

 

백준 16365번 Square root www.acmicpc.net/problem/16365

16365번: Square Root

풀이를 생각하는 것은 그렇게까지 어렵지는 않았다. 근데 이 문제도 구현이 조금 힘들 것 같다.

[관찰 1] G의 한 점에서 거리가 2인 점을 구한다. 이때, 거리가 2인 점에 도달하는 방법이 두가지이면, T에서 거리가 3인 점이고, 방법이 한가이지면, T에서 거리가 4인 지점이다. 또, 한 점에서 거리가 3인 점과 4인 점들 사이에 간선이 있다면, 그것은 T에서의 간선이다.

[풀이] 트리의 지름이 4 이하인 것과 아닌 것으로 나눠서 푼다. 이를 위해 서로 다른 세 점을 임의로 골라 위의 관찰에서 처럼 bfs를 해주자.

1) 그 세개 중에서 거리가 3인 점이 없다면, 지름이 2인 트리이다. 나머지 분석은 쉽게 할 수 있다.

2) 그 세개 중에서 거리가 4인 점이 있으면, 지름이 4 이상인 트리이다.

3) 그 세개중에서 거리가 4인 점은 없으나, 거리가 3인 점이 있다면 지름이 3인지 4 이상인지를 다음과 같이 판단해준다.

한 점에서 거리가 3인 점을 모두 흰색으로 칠했다고 하자. 흰색 점중 아무 점을 골라잡고 마찬가지로 bfs를 돈다. 거리가 4인 점이 있다면, 지름이 4 이상인 트리이고, 아니면 지름이 3인 트리이다.

지름이 3인 트리는 또한 쉽게 체크할 수 있다.

이제 지름이 4 이상인 경우만 보자. 앞의 경우에서 지름이 4 이상인 경우는 거리가 4인 두 점을 찾았을 때였으므로, 이미 두 점이 지름이 4인 점이라고 해보자.

 

 

이 때, 가운데 점은 나머지 네 점과 모두 연결되어있고, 이러한 점은 유일하다.

따라서 우리는 T에서 네개의 연결된 간선들을 얻을 수 있다. 이것을 시작으로 해서 전체 트리를 복구할 것이다.

[관찰 2] T상의 연속된 세개의 점 1, 2, 3에 대해서 1, 2와 동시에 연결되어있으나 3과 연결되어있지 않은 노드는 트리에서 1과 연결되어야한다.-->O(deg(1)+deg(2))

이 관찰로 트리를 전부 복구시킨다.

 

마지막으로 복구시킨 트리 T에 대해서 T^2이 G와 같은지 확인한다.

관찰 2의 트리 연장의 시간복잡도를 따져보면, deg(i)가 상수번 쓰이게 해야 시간초과가 안나는데, 이건 대충 잘 하면 된다.

마지막 문제는 풀이에 틀린점이 있으면 지적 부탁드립니다.
-> proved by ac.
디그리가 대충 sqrt(1e5)이라는 성질을 이용하면 아무렇게나 dfs를 해도 시간초과가 안뜨는것 같다.(증명을 안해봤다. 실전에서는 짜면 그냥 내야지.. 이정도 고퀄의 저격데이터는 없겠지..?)