티스토리 뷰

http://codeup.kr/JudgeOnline/problem.php?id=4854

데이터 만들기 어려워보이는 문제다 ㅠㅠ


일반성을 잃지 않고 s < e로 하자. 증명이 많은데 별로 안 엄밀함. (노력은 했다.)

서브태스크 2 (51점)

일단. 모든 점을 볼 수 있는 점이 하나라도 존재한다면, s -> e로 가는 최단 경로는 [s, e] 구간을 볼록하게 잇는 (오른쪽으로 계속 회전하는 방향의) 체인이 됨을 알 수 있다. 이는 컨벡스 헐과 동치이다.


증명 : 자명하게도, [s,e] 구간에 있는 점들만 고려해서 만든 convex chain보다 더 짧은 경로는 절대 만들 수 없다. 그 경로를 항상 만들 수 있음을 보일 것이다.

1. [s,e] 안에 있는 점들이 만약에 볼록 껍질 상 경로를 방해했다면. 볼록 껍질이라는 전제에 모순이 생긴다. 고로 이는 일어날 수 없다.

2. 이제 그 외의 점이 이 점을 건드릴 수 없음을 보일 것인데, 컨벡스 헐 상의 인접한 두 점 i, j(i < j)에 대해 (0, i, j) 점을 잇는 삼각형을 고려해보자. 앞의 가정을 만족하면서 (i, j) 간의 직선을 파괴하려면 (0, i) 나 (0, j) 상의 직선이 파괴되어야 하고, 그렇다면 모든 점이 볼 수 있다는 가정이 모순이다. 고로 최소 경로는 항상 가능하다.

3. i나 j가 0일 경우에는 자명히 직선으로 이으면 되니 컨벡스 헐이 역시 먹힌다.


만점

일단 위 51점 코드를 짰다면 여기서는 보통 WA가 나온다. 위쪽 마지막 문단의 증명을 검토하자.

1. 인접한 두 점 i, j가 같은 점에 의해 도달가능하면 증명은 동일하다.

2. i는 0번 점. j는 1번 점만 볼수 있다고 하자. 하지만 여전히 (i, j) 간 직선을 파괴하려면 (0, i) 나 (1, j)를 지나야만 한다. 다시 한번 가정에 모순. '

3. i나 j가 0 / 1일 경우는 케이스가 또 몇개 있다.

3 - 1. 둘다 0 - 1이면 자명하다.

3 - 2. 하나만 1이면, 만약 나머지 점이 0에 의해 도달가능하면 [1, j] 컨벡스헐. 아니면 1에 의해 도달 가능하니 자명하다.

3 - 3. 하나만 0이면, 만약 나머지 점이 1에 의해 도달가능하면 [j, 0] 컨벡스헐. 아니면 0에 의해 도달 가능하니 자명하다.


3-3 케이스를 처리하기 위해서. a(n) = a(0)으로 두고. 두 정점 중 하나가 0일 경우 무조건 n으로 바꿔두자. 그러면 풀린다.

cpp : https://gist.github.com/koosaga/a6f6c04fb5d22066cc0f

'공부 > Problem solving' 카테고리의 다른 글

시간이 돈 (Balkan OI 2011)  (0) 2015.12.28
케이크 (JOI Spring Camp 2013)  (0) 2015.12.27
Toys (USACO Nov 08 Gold)  (0) 2015.12.13
나는코더다 활동자료  (0) 2015.12.08
Tourists (Codeforces 487E)  (2) 2015.11.15
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday