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
http://codeforces.com/contest/487/problem/E 문제 설명은 생략함. HLD + BCC를 섞은 문제로써 헬문제였따.. 풀이를 대충 요약하겠다. BCC 파트가 제일 어려웠는데, 지금 열거하는 방법으로 BCC를 트리로 묶어줄 수 있다. 꽤나 스탠다드한 방법이 아닐까 싶다. 익혀두자. * 1. Cut Vertex + BCC Component가 정점이 된다.* 2. Cut Vertex와 연결된 BCC Component를 이어줌으로써 트리를 만든다. * 3. BCC Component에서 DFS Number가 가장 높은 애를 BCC Parent라고 정의한다. 이건 내가 쓴 BCC 알고리즘에서, 처음 새 컴포넌트를 spawn한 노드와 동치라고 할 수 있다. * 4. 문제 특성상 각각의 ..
- Total
- Today
- Yesterday