1개의 댓글이 있습니다.
-
-
cki86201 -
먼저 선형에 대해 생각해 봅시다.
다른 색의 점을 이은 두 구간 (l1,r1), (l2,r2)에 대해, 이들이 적당히 겹칠 경우(가령, l1<l2<r1<r2.) 이를 분리할 수 있습니다. 이렇게 할 경우 임의의 두 구간에 대해, 두 구간은 다음 둘 중 하나의 관계를 가집니다.
i) 한 구간이 다른 구간을 완전히 포함합니다.
ii) 서로 교집합이 없습니다.서로 매칭된 두 점 P, Q에 대해 P와 Q 사이의 붉은 점의 개수와 푸른 점의 개수는 같습니다.
임의의 붉은 점 P에 대해, 2번 조건을 만족하는 점들 중 2개(혹은 그 이하)만 보면 됩니다. 이 두 점은 각각 오른쪽으로 가장 가까운 점, 왼쪽으로 가장 가까운 점입니다.
pf> 2번 조건을 만족하는 두 점 Q1, Q2(P<Q1<Q2)에 대해, 어떤 점 P'(Q1<P'<Q2)이 있어 P', Q2가 2번 조건을 만족합니다. 이 때 P-Q1, P'-Q2를 잇는 것이 P와 Q2를 잇는 것보다 더 이득입니다. 따라서 Q2는 P와 이을 필요가 없고, Q1만 보면 됩니다.임의의 푸른 점 Q에 대해, 3번 조건을 만족하는 붉은 점은 양쪽에 많아야 하나씩 존재합니다.
pf> 3번 조건을 만족하는 두 점 P1, P2(Q<P1<P2)이 있다고 가정합시다. 이 때 어떤 점 Q'(P1<Q'<P2)가 있어, P2와 Q'이 2번 조건을 만족합니다. 따라서 P2와 Q가 3번 조건을 만족함에 모순입니다.따라서 3번 조건을 만족하는 쌍들을 이으면 푸-붉-푸-붉-...-붉-푸 /이런 식으로 이어지게 됩니다. (끝 점의 색은 둘 다 가능하지만, 두 끝점이 전부 붉은색일 수는 없습니다.) 가능한 방법은 선형 개수이고, 전부 해 보면 됩니다.
따라서 O(N)에 됩니다! 구현은 그리 어렵지 않으니 따로 적지 않겠습니다.
원형도 같은 방식으로 생각하면 풀릴 것 같네요ㅋㅋ
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Qwaz
문제는 여기서 받으실 수 있습니다.
http://acm.kaist.ac.kr/2012/MainContest/2012Problems.pdf
KOI 2005년 기출문제인 '소방차'라는 문제를 풀다가 잘 풀리지 않아 찾아보던 도중, 2012년 대전 리저널에서 유사한 문제인 가속기라는 문제가 출제되었다는 것을 알게 되었습니다.
간단하게 설명드리자면 가속기의 경우 원형, 소방차의 경우 선형 1차원 공간 위에 두 종류의 점들이 주어지고 서로 다른 종류의 점들을 각각 매칭을 하는데 매칭되는 점들 사이의 길이의 합을 최소화하는 문제입니다.
동적 계획법 등의 접근 방법을 생각해보았으나, O(N^2) 이하의 시간복잡도를 가지는 풀이를 찾을 수 없어 질문을 올리게 되었습니다.
10년 전