2016.02.11 problem solving

Hill Walk (USACO 2013.03 Gold)

https://www.acmicpc.net/problem/5835

x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 

저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다.

1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%EC%9A%A9%EB%B2%95 를 참조하면 해결할 수 있는데, 더 좋은 방법이 있다. c++11의 decltype() 라는 문법을 사용해서, 다음과 같이 편리하게 코딩할 수 있다. (왜 되는지는 모른다.)

저렇게 했더니 언어가 x랄을 하지 않았고, 고로 코드는 상당히 짧다. https://github.com/koosaga/olympiad/blob/master/USACO/mar13_hill.cpp

벽 쌓기 (Croatian IOI Selection 2010)

https://www.acmicpc.net/problem/3105

다른 디테일은 생략하고 이 부분만 짚고 넘어가겠다. 이 작은 문제가 문제 전체를 푸는 것의 핵심이다.

* N <= 100 개의 블럭이 크기 Di, 가격 Wi를 가진다. (1 <= Wi, Di <= 1000) 한 블럭을 여러 번 집을 수 있을 때 크기가 정확히 C인 가장 값싼 블럭 구매 방법은? (C <= 10^9)

C가 10^9이기 때문에 쉽지 않은데, 생각해보면 가장 가성비가 좋은 블락을 최대한 많이 사는 것이 보통 이득일 거라는 것을 눈치챌 수 있다. 그리고 W와 D가 충분히 적기 때문에 전부는 아니더라도 꽤 많이 살수 있을 것이고... 결론부터 말하자면, C > 1000000 일때는 무조건 가성비가 가장 좋은 것을 사고, 그렇지 않을 경우에는 냅색으로 문제를 해결하는 것이 문제의 해결 방법이다.

증명은 다음과 같다. 가성비가 가장 좋은 원소의 크기를 Di라고 하면, 임의의 해집합 S에서 크기가 Di의 배수인 부분집합을 골라서 이걸 모두 가성비가 가장 좋은 놈으로 바꾸면 항상 해를 같거나 좋게 개선시킬 수 있다. 비둘기 집의 원리를 사용하면, 어떤 상황에서 Di개의 블럭이 존재 시 여기서 크기가 Di의 배수인 부분집합을 무조건 고를 수 있다. 고로 C <= Wi * Di 이상일 때는 항상 가성비가 가장 좋은 놈을 1개 이상 사용하는 최적해가 존재.

울타리 (Croatian IOI Selection 2009)

https://www.acmicpc.net/problem/3119

문제를 처음 보면 대략 정신이 멍해지는데.. 일단, 모든 높이가 같을 때는, 그때 그때 끝점이 가장 큰 원소를 뽑는 그리디가 가능하다. (말이 그리디지 증명도 매우 쉽고 굉장히 당연한 방법이다. DP라고 생각해도 결과는 비슷하다.) 여기서 일반화를 시키면 문제를 풀 수 있다.

초기에 전체 판자의 skyline을 O(nlgn)에 스위핑으로 구한 후, 스카이라인을 차근 차근 메꿔나가자. 이제 다음과 같이 그리디를 시작한다.

* 아직 판자로 덮여지지 않은 가장 왼쪽 skyline을 생각했을 때, 그 skyline과 높이가 같으면서 가장 끝점이 큰 원소를 뽑아서 덮어준다.

앞에서 언급한 알고리즘의 자연스러운 일반화로써, 적절한 자료구조를 사용시 O(nlgn)에 문제를 해결할 수 있다.

택배 배달 (COCI 2008/2009)

https://www.acmicpc.net/problem/2939

일단 왼쪽 오른쪽 끝을 정점으로 두고 all pair shortest path를 계산해두면 몇가지 casework를 통해서 N^2lgN 정도에 문제를 해결할 수 있다. 이걸로 TL이 뜨리라고는 상상하지 못했는데 뜨더라.

때문에 그래프의 특수한 성질을 사용해서 O(N^2)에 all pair sp를 계산해야 한다. 먼저 왼쪽 끝 - 오른쪽 끝으로 가는 shortest path를 O(N^2)
에 계산하자. (올라갔다 내려가고, 내려갔다 올라오고... 후보는 N개이다.) 이러한 shortest path를 알면 i < j로 지나가는 shortest path는 i+1 < j로 지나가는 shortest path를 항상 거쳐야 함을 알 수 있고, 따라서 재귀적으로 구성해나가면 된다. (dp 비슷하게.)

KTX 열차 기지 (Daejeon 2010)

https://www.acmicpc.net/problem/8921

다 필요없고 결과만 생각하면 아주 복잡한 문제가 아니다. (난 그렇지 않아서 아주 복잡하게 접근했고 처절히 말렸다.. ㅠㅠ) 일단 처음 간파해야 할것은 들어오는 시간과 나가는 시간의 부호가 항상 음수 / 양수라는 것이다. 결과적으로 중간에 기찻길에 저장되는 기차의 형태는 -

[-1W, 3W] [-5W, 7W] [-7W, 8E] [-9W, 7E] [-6E, 3E] [-2E, 2E]

[-1W, 3W] [-5W, 7W] [-10E, 9W] [-8E, 11W] [-5E, 6E] [-2E, 2E]

이런 식인데, 시작 인덱스와 끝 인덱스 모두 W(절댓값 증가) + E(절댓값 감소) 의 양상을 띔을 알 수 있다. 그리고 어떤 형태의 기차던간에 그러한 양상만 만족한다면 한 선에 저장할 수 있음을 알 수 있다. 이렇게 생각하면 시작 인덱스와 끝 인덱스를 그냥 번호로 저장해도 된다.

(1, 3) (5, 7) (7, 1e9 - 8) (9, 1e9 - 7), (1e9 - 6, 1e9 - 3) (1e9 - 2, 1e9 - 2)

(1, 3) (5, 7) (1e9 - 10, 9) (1e9 - 8, 11) (1e9 - 5, 1e9 - 6) (1e9 - 2, 1e9 - 2)

최소한의 increasing sequence들을 통해서 모든 점을 덮는 문제는 잘 알려진 문제이다. (permutation graph coloring) http://koistudy.net/?mid=prob_page&NO=385