구사과

http://codeup.kr/JudgeOnline/problem.php?id=4854데이터 만들기 어려워보이는 문제다 ㅠㅠ 일반성을 잃지 않고 s e로 가는 최단 경로는 [s, e] 구간을 볼록하게 잇는 (오른쪽으로 계속 회전하는 방향의) 체인이 됨을 알 수 있다. 이는 컨벡스 헐과 동치이다. 증명 : 자명하게도, [s,e] 구간에 있는 점들만 고려해서 만든 convex chain보다 더 짧은 경로는 절대 만들 수 없다. 그 경로를 항상 만들 수 있음을 보일 것이다. 1. [s,e] 안에 있는 점들이 만약에 볼록 껍질 상 경로를 방해했다면. 볼록 ..

https://www.acmicpc.net/problem/1156https://www.acmicpc.net/problem/6065 이 문제 데이터 오류가 있다. 대회 당시 워낙 어려웠던 문제라 이의제기가 안됐을 뿐... http://blog.myungwoo.kr/6 O(N^2Ti) 일단 관찰 하나가 필요한데, 그 날이 끝났을 때 굳이 소독을 어떻게 맡길지 결정할 필요는 없다. 장난감이 필요할 때마다, 그전 상황을 끼워맞춰 가는 식으로 최대한 이득을 보는 상황을 결정하는 것이 필요하다. 그 전날에 상황을 끼워맞출 수 있는 가짓수는 크게 세가지가 있는데 * 1. 장난감을 새로 샀다고 생각 * 2. 그 전에 썼던 장난감을 1번 소독소에서 가져왔다고 생각 * 3. 그 전에 썼던 장난감을 2번 소독소에서 가져왔다..

https://github.com/koosaga/iamcoder