티스토리 뷰

ICPC/2014 대전

E. Marbles

전명우 2014.11.09 22:57

빨강, 파랑, 초록색, 세 가지 색상의 공들이 2차원 평면에 배치 되어 있다. 빨간색 공을 세는 직사각형, 파란색 공을 세는 직사각형, 초록색 공을 세는 직사각형 세 개를 크기 제한 없이 겹치지 않게 잡았을 때 세어지는 공의 개수를 최대화 하는 문제다. 여기서 직사각형 변 위에 있는 공도 세어주고, 겹쳐서는 안된다.


우선 직사각형의 크기 제한이 없다는 점을 생각하자. 그러면 가능한 직사각형의 배치를 아래와 같이 크게 두 가지로 나눌 수 있다.


        


이 두 가지 경우에 대한 코딩을 하고 y축 대칭, 직선 y=x에 대한 선대칭 및 $3! = 6$가지의 색상 재배열등을 행해 모든 경우를 고려할 수 있다.


우선 각 점들을 x 좌표 기준으로 정렬을 한 뒤 빨간색 영역이 차지하는 범위를 정한 뒤 segment tree 자료구조를 이용해 파란색과 초록색 영역이 적절히 나눠졌을 때 최대값을 구한다. 기본적인 아이디어는 초록색 점에게 1의 가중치를 주고, 파란색 점에게 -1의 가중치를 주어, 파란색 점의 개수를 미리 세주고 최대의 가중치를 포함하는 영역을 구하는 방법이다.


자료구조에서 점의 위치를 2차원이 아닌 1차원으로 표현할 수 있고, 각 좌표에 가중치를 더하는 작업이 $O(\lg N)$, 영역이 갖는 최대 가중치 값을 $O(1)$에 계산할 수 있다. 영역은 1차원 좌표계의 중간이 아니라 처음과 중간 지점까지 연속한 영역을 고려하면 되므로 최대 가중치 값을 찾는 작업이 $O(1)$에 수행될 수 있다.


코드 보기


'ICPC > 2014 대전' 카테고리의 다른 글

G. Road Repair  (0) 2014.11.10
F. Permutation Cycles  (0) 2014.11.09
E. Marbles  (0) 2014.11.09
D. Exploration  (2) 2014.11.09
C. Eureka Theorem  (0) 2014.11.09
B. Deduction  (0) 2014.11.09
댓글
댓글쓰기 폼