구사과

https://www.acmicpc.net/problem/2795딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자. 일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를..

Hill Walk (USACO 2013.03 Gold)https://www.acmicpc.net/problem/5835x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다. 1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%E..

Water Tree (CF 343D)http://codeforces.com/problemset/problem/343/D거꾸로 생각한다. 기본적으로 모든 노드에 물이 채워져 있고, 1 ~ N개의 노드에 물을 비우는 연산을 넣어 줬다고 가정하자. 비우는 연산이라 함은 해당 노드와 그 부모에 있는 물을 모두 제거함을 뜻한다. * Query 1 : v의 서브트리에, 물이 비우는 연산이 적용되어 있는 노드가 있다면, 모두 지워주고, v의 부모에 물을 비우는 연산을 적용한다. * Query 2 : v에 물을 비우는 연산을 적용한다. * Query 3 : v의 서브트리에 물이 비우는 연산이 적용되어 있었다면 0, 아니면 1을 출력한다. 문제가 아주 깔끔해졌으며, dfs number 순서대로 수를 보관해두면, 세그먼트..