USACO Platinum - 2

벌써부터 점점 풀기가 어려워지고 있다.

14446. Promotion Counting

15899번 문제와 완전히 똑같은 문제. 이제는 너무 널리 알려진 테크닉이 아닌가 싶다.

 

 일단 오일러 투어 테크닉을 써서 트리를 배열로 펴주고 나면 각각의 서브트리를 구간으로 나타낼 수 있다. 이제 이 구간에서 루트의 값 x보다 큰 원소의 개수를 세는 문제가 되는데, 이는 여러 가지 자료구조를 이용해서 풀 수 있다. 나는 그냥 머지소트 트리 써서 풀었다.

14522. Modern Art(Platinum)

 문제를 잘못 읽어서 약간 헤맸다. N^2개 수를 각각 최소한 한 번씩 쓴다는 조건이 있는데 이것 때문에 생기는 예외를 처리를 안 했음.

 

 우선 각각의 색에 대해 그 색이 칠해진 사각형 영역의 크기를 구한다. 이 사각형 영역 내에 있는 다른 색깔은 제일 먼저 그려질 수가 없는 색이다. 이제 이 판단을 어떻게 해야 빨리 할 수 있느냐가 문제인데, 이차원 부분합 개념을 이용하면 어떤 위치 x를 칠한 사각형이 두 개 이상일 때, 이 칸에 그려진 색은 맨 처음 그려질 수가 없는 색이다. 최소한 그 칸을 두 번 이상 색칠을 했는데 마지막에 남아있는 색이라는 말은 다른 색을 칠하고 덮어 씌운 색이라는 의미이기 때문이다.

 

따라서 O(N^2)에 문제를 해결할 수 있다. 여기서 모든 색을 한번씩 쓴다는 조건 때문에, 색이 하나밖에 없는 경우 이 색이 다른 색을 덮어 씌운 색이므로 이 색을 답에서 제외해야한다는 예외가 생긴다(N=1이 아닌 경우).

11991. Fenced In(Platinum)

 나는 생각하기가 굉장히 힘들었는데 다른 사람들은 좀 쉬웠나 보다. Modern Art는 다른 사람들이 준 난이도에 비해 좀 쉽다고 느꼈고 이 문제는 굉장히 어렵다고 느꼈다. 내가 약한 부분인 것 같기도 하다.

 

 문제는 결국 (N+1)(M+1)개의 노드로 구성된 그리드 형태의 그래프에서 MST를 찾는 문제가 된다. 이때 일일히 간선을 지워나가면서 MST를 구하려고 하면 시간복잡도가 O(MN)에 비례하게 되기 때문에 싸이클을 형성하는 간선을 빠르게 제거하는 규칙을 찾아야만 한다.

 

 이 때 잘 생각해보면 항상 지워지는 간선이 연속한 한 변을 구성하는데, 연속한 좌우 한 변과 상하 한 변을 최소 한 번 이상씩 제거한 경우 한 번 변을 지울 때마다 반대 편 변에서 쓸 수 있는 간선의 크기가 1씩 줄어든다. 이 성질을 이용해서 남아 있는 변의 길이(해당 변에 속하는 간선의 개수)를 업데이트해가며 문제를 해결하면 O((N+M)log(N+M)) 시간에 문제를 해결할 수 있다.