구사과

http://oj.uz/problems/view/JOI13_cake이런 문제를 내는 사람이나 푸는 사람이나 신기하다. Preliminaries1. 저 그대로의 폼으로는 딱 봐도 답이 안 나오는 구조다.. 거꾸로 들어가야 한다. 어떤 원소 T를 먼저 고르고 들어갔을 때, 마지막으로 먹는 원소는 무엇인가? 답은 T가 아닌 가장 작은 수임을 쉽게 알 수 있다. 최솟값을 고르고 들어갔을 때는 O(N)에 계산하는 예외처리를 해주자. 나머지 경우에는 항상 최솟값이 마지막으로 남을 것이다. 최솟값이 a[0]에 저장되어 있다면 선형에 대해서 문제를 풀어주면 된다. 이건 std::rotate를 쓰면 되니까 O(N)에 원이 선형으로 풀렸다.2. 그래서 마지막에 먹는 걸 누가 먹는지 알았는데, 나머지는 어떻게 알까? 나머지..

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번 소독소에서 가져왔다..