USACO Platinum - 1

USACO 플래 문제 밀기를 하고 있다. 쉬운 난이도부터 정렬해서 푸는 중.

11979. Fort Moo

부분합을 구해두면 O(N^2M^2)은 쉽게 생각할 수 있다. 사각형을 이루는 네 꼭지점을 정한 뒤 그 네 변의 어디에도 X 표시가 없으면 답을 갱신해주는 걸 반복해주면 되기 때문. 여기서 N 혹은 M을 하나 떼면 시간 안에 돌아가는 시간 복잡도가 된다.

 

 좌우 부분합, 상하 부분 합은 세제곱 베이스로 계산이 가능하기 때문에 부분합까지는 똑같이 구한다. 사각형의 위아래 변만 고정하면 O(N^2)이 되는데, 여기서 윗변과 아래변을 연결하는 X 자 표시가 없는 직선의 위치는 부분합을 이용하면 O(M)에 전처리가 가능하다.

 

 이렇게 구해놓은 각 직선끼리 최대한 윗변 or 아랫변에서 X가 없는 조건을 만족하면서 이어주면 되는데, 이런 형태의 최대 크기 사각형은 투 포인터 개념을 이용하면 O(M)에 계산이 가능하다. 따라서 O(N^2M) 의 시간복잡도로 문제를 해결할 수 있다. 

14165. Team Building

 먼저 각 팀의 실력을 크기 순으로 정렬하자. 그 다음 아래와 같은 DP 식을 세운다.

 

DP(i, j, k) = A팀에서 i..n, B팀에서 j..n 까지만 고려했을 때, 조건을 만족하며 K명을 뽑는 경우의 수

 

이렇게 정의하고 DP(i, j, k)의 식을 유도해보자.

 

1. a[i] > b[j]인 경우 : 이 경우 i와 j를 한 번 짝 지을 수 있다. 둘을 짝 지은 다음 경우의 수는 DP(i + 1, j + 1, k - 1)이 된다.

2. 기본적으로, a의 i번째 혹은 b의 j번째를 버릴 수 있다. 이 경우는 DP(i + 1, j, k) + DP(i, j + 1, k)가 된다. 이 때 DP(i + 1, j + 1, k)는 양쪽에서 모두 한 번씩 계산하므로 서로 중복이 되는 경우다. 따라서 이 경우를 빼주면 DP(i + 1, j, k ) + DP(i, j + 1, k) - DP(i + 1, j + 1, k)가 된다.

 

이렇게 정의할 경우 O(NMK)의 시간복잡도로 문제를 해결할 수 있다.

11962. Counting Haybales

Segment Tree With Lazy Propagation의 연습 문제다. 합과 최솟값을 쿼리하는 연산과 지정된 범위에 k를 더하는 연산 두 가지를 지원하는 Segment Tree를 만들면 O(N+QlogN)에 문제를 해결할 수 있다.

11960. Max Flow

트리의 각경로를 부분합처럼 생각한다. s -> t 로 가는 경로는 둘의 LCA를 l이라고 했을 때 s -> l -> t 로 볼 수 있는데, 부모를 따라 가는 경로를 기준으로 생각하면 s -> l 경로와 t -> l 경로에 해당하는 모든 정점에 값을 1씩 더해주는 걸로 생각할 수있다. 이 때 l 지점에는 값이 2가 더해지게 되니 1을 한 번 빼주어야 한다. 따라서 flow[s]에 +1, flow[t]에 +1, flow[l]에 -1, flow[par[l]] 에 -1을 해준 후 리프노드부터 따라올라가면서 부모의 flow에 자신의 flow를 더하는 것을 반복해주면 모든 정점의 flow값을 계산할 수 있다. LCA를 구해야하기 때문에 시간 복잡도는 O(NlogN)이 된다.

17018. Redistricting

O(NK) DP 식은 쉽게 유도할 수 있다. 여기서, 내가 이번에 새로 만들 구간으로 인해 값이 +1이 되는지 아닌지를 구분해서 처리하는 것때문에 최적화하기가 힘들다. 나는 조금 복잡하게 풀었는데, diff[i] = (1..i에서 G개수 - H개수)라고 정의하면 내 앞의 j번 인덱스중 diff[i] >= diff[j] 를 만족하는 경우 값이 +1이 되고 그렇지 않으면 값이 추가되지 않는다. 따라서 diff[i]를 기준으로 양쪽 구간에 해당하는 인덱스를 앞의 k 범위에 대해서만 유지해주면 되는데, diff[i]를 기준으로 구간을 나눠서 O(logN)에 쿼리하는 건 세그먼트 트리로 쉽게 할 수 있다. 앞의 k만 유지하면서 갱신해주는 건 데크를 이용해서 관리해주었다. 이렇게 최적화하면 O(NlogN)에 문제를 해결할 수 있다.

12008. 262144

재밌는 문제였다. 근데 나는 좀 복잡하게 풀었다.. Sparse Table로 풀릴까 살짝 고민하고 넘어갔는데 실제로 Sparse Table로 풀리는 문제였다. 나는 조금 다르게 접근해서, 배열을 링크드 리스트 형태로 연결한 다음, 배열에서 값이 가장 작은 위치부터 시작해서 좌우에 해당 위치를 붙일 수 있는지 검사하는 식으로 풀었다. 이렇게 붙이는 과정에서 만약에 짜투리가 반드시 남게 되는 경우, 그 위치 왼쪽과 오른쪽을 서로 연결할 수 있는 방법은 없다. 그래서 이런 경우 리스트를 양쪽으로 끊어서 해당 위치를 왼쪽에 붙이는 경우 오른쪽으로 붙이는 경우를 따로 따로 처리하게 하는 식으로 풀었다.

14164. 삼각형 영역

내가 약한 기하 문제라서 정말 어렵게 풀었다. ccw를 이용해 점들을 직선 기준으로 왼쪽 or 오른쪽에 있는지 분류해서 풀면 될거 같다는 아이디어는 금방 떠올렸는데, 여기에 좀 더 제약을 둬야한다는 걸 생각하는데 한참이 걸렸다. 그냥 직선을 기준으로 하면 안 되고 선분을 기준으로 선분의 위 아래를 잘라서 해당 선분의 y 좌표 범위 내에 있는 점에 대해서만 개수를 세주어야 한다. 그래서 점을 y가 증가하는 순으로 정렬해놓고 풀면 구현이 좀 쉬워진다.

 

이렇게 정렬하면 count[i][j] = i ~ j 두 점이 이루는 직선 왼편에 있는 점의 개수 라고 정의할 수 있고, 모든 i, j에 대해 이걸 계산하는 건 O(N^3)이면 충분하다. 이렇게 구해두면 점 i, j, k가 이루는 삼각형은 count[i][j] 와 count[j][k], count[i][k] 세 개의 값을 이용해 식을 유도할 수 있다. 이 때 i, j, k 가 이루는 방향에 따라서 식이 조금씩 달라지기 때문에 이 부분을 잘 처리해서 문제를 풀어야 한다.