USACO Platinum - 4

 이제 플래티넘 이하 난이도 문제는 총 3개가 남았다. 내일 모레쯤 끝날 듯. 다이아는 천천히 풀어야지(천천히 풀기 싫어도 천천히 풀게 되겠지)

18260. Bessie's Snow Cow

 내가 비교적 잘 푸는 유형이라 쉽게 풀었다.

 

 이 문제도 일단 오일러 투어 테크닉을 써서 구간으로 펴서 생각한다.

 

 이렇게 펴서 생각하면, 업데이트는 특정 구간에 색깔 c가 없는 위치에 전부 c를 추가하는 연산으로 생각할 수 있다. 쿼리는 그 구간에 존재하는 색 개수의 합을 구하는 형태가 되는데, 여기까지만 놓고 보면 제일 기본적인 형태의 Lazy propagation Segment Tree로 생각할 수 있다. 다만 색깔 c가 없는 위치만 골라서 c를 추가하는 부분이 조금 어려운데, 여기서 각 구간이 하나의 서브 트리를 나타낸다는 점을 생각하면 이걸 조금 쉽게 처리할 수 있다.

 

 각 색깔 c에 대해서 기존에 그 색깔 c로 칠해진 구간을 colored[c] 라는 set에 넣어서 관리한다고 생각하자. 그러면 이번에 쿼리로 업데이트되는 부분에 대해, 기존 colored[c]에 들어가있는 구간은 1. 이번에 업데이트할 구간을 완전히 포함하거나 2. 이번에 업데이트할 구간에 완전히 포함되거나 둘 중하나의 조건을 반드시 만족하게 된다. 모든 서브트리들은 서로 포함 관계를 가지지 서로 구간이 걸치는 경우는 존재하지 않기 때문이다.

 

 따라서 기존에 colored[c]에 들어가 있는 구간 중 이번에 업데이트할 구간에 포함되는 모든 구간을 제거해주고(해당 구간에 -1해서 기존에 더했던 걸 취소) 이번 구간을 추가해주면 된다. 이렇게 할경우 각 쿼리로 인한 구간이 최대 한 번만 더해지고 한번만 제거되기 때문에, O((N+Q)logN) 시간에 문제를 해결할 수 있다.

18777. Delegation (Platinum)

 처음 좀 잘못된 접근을 한 다음 그걸 고치는데에 너무 많은 시간을 썼다. 큰 그림은 맞았는데 작은 범위에서 결정 함수를 설계하는 걸 너무 잘못 했다.

 

 어떤 값 K에 대해 최소 K 이상의 path로 트리를 분할하는게 가능하다면, K-1이상의 path로 트리를 분할하는 것도 가능하다. 따라서, K 값에 대해 파라메트릭 서치를 할 수 있다. 그러면 이제 K 값을 고정된 변수로 생각하고 이 K에 대해 주어진 트리를 K 이상의 path로 분할하는게 가능한지 판별한다고 생각해보자.

 

 트리를 여러 path로 분할할 때, 어떤 트리에서 그 트리의 서브트리 -> 해당 트리의 부모를 잇는 path는 단 한가지만 존재할 수 있다. 즉, 각각의 트리는 자신의 sub tree에서 시작하는 path중 어느 하나를 골라 자신의 부모쪽 간선과 연결하는 방식으로 분할이 이루어진다. 이 때, 그 sub tree 내부에서 최소 k 이상의 path로 전부 분할이 가능하면서, 남는 경로중 최대한 길이가 긴 것을 부모쪽에 이어주는게 이득이다. 어차피 k 이상 조건은 만족하면서 부모 쪽에서 더 좋은 선택을 할 수 있기 때문이다.

 

 따라서 이 조건을 만족하는 가장 긴 값을 리턴하게끔 dfs를 구성하면 되는데, 이 값을 구하는 로직을 설계하는 것에서 한참 헤맸다. 일단 자식으로부터 받아온 경로 길이 값에 대해 전부 k 이상의 길이를 유지하면서 짝지어주는게 가능한지 판별하는 방법을 생각해보자. 경로 길이를 전부 정렬하고 나면 가장 작은 것은 가장 큰것, 그다음으로 작은 것은 그다음으로 큰 것, ... 을 순서대로 이어주는게 최선이다. 즉 정렬이 되어 있다면 자식 개수가 C라고 했을 때 O(C) 시간에 그리디하게 판별이 가능하다.

 

그런데 이 중에서 경로 하나는 빼서 내 위쪽으로 보내고 싶으므로, 경로 하나를 제외하고도 저게 가능한지 체크해서 가능하면 그 경로를 부모쪽으로 보내면 된다. 여기서 이것도 다시 파라메트릭 서치로 수행할 수 있다. 따라서 전체 시간 복잡도 O(Nlog^2N)에 문제를 해결할 수 있다. 이 때 나는 자식 개수가 홀수 개 남았을 때 그리디 조건을 조금 잘못 생각해서 한참 헤맸다. 한개 남는걸 중간에서 꺼낸다고 생각했는데 이걸 맨 오른쪽 끝으로 쓰는게 더 좋은 결과값을 낸다.. 당연한건데 이걸 그냥 짝수일 때만 생각하고 홀수 개일때는 가운데 남는게 맞겠지 하고 넘어갔다. 사고의 매 스텝에서 정당성을 생각하는 훈련이 아직도 덜 된 것 같다.

15585. Sprinklers

 이것도 구체적인 식을 세우는데 시간이 너무 오래 걸렸다. 중간에 좀 많이 뇌절했다가 돌아온 듯. 문제는 재밌었다.

 

 스프링쿨러에서 물도 받고 비료도 받는 영역을 구해서 그 영역 내에서 사각형을 구성할 수 있는 경우의 수를 센다고 생각해보자. 물을 받는 영역은 스프링쿨러의 좌하 영역이고, 비료를 받는 영역은 스프링쿨러의 우상 영역이다. 이 때 우선 스프링쿨러의 좌표를 x축을 기준으로 정렬해보자. 각 x 값마다 정확히 하나씩의 스프링쿨러가 있으므로, 이렇게 정렬하고 y좌표만 놓고 보면 1차원 배열로 생각할 수 있다.

 

 이 때 비료를 받는 영역은 항상 주어진 좌표의 오른쪽, 위쪽 영역을 모두 채우기 때문에, 자신의 왼쪽 아래 영역에 스프링쿨러가 이미 설치되어 있는 경우 그 스프링쿨러는 아무런 영향을 끼치지 못한다. 이를 이용하면 각 x좌표에 대해 비료를 받을 수 있는 가장 아래쪽 좌표를 f[x] 라고 했을 때, f[x] = min(p[x - 1], y) 가 된다. 최대한 아래쪽으로 선택하는게 이득이기 때문이다.

 

 물을 받는 영역도 비료를 받는 영역과 대칭이기 때문에, 비슷한 방법으로 구할 수 있다. x 좌표에서 물을 받는 영역은 w[x] 이하의 y 좌표라고 하자. 이렇게 할 경우, 각각의 x에 대해 f[x] ~ w[x] 사이의 y좌표는 물과 비료를 모두 받는 영역이 된다. 이 때, f[x-1] >= f[x] 이고 w[x-1] >= w[x] 이다. 즉, 이 영역은 점점 더 아래쪽으로만 이동한다. 이건 그림으로 그려보면 왜 그렇게 되는지 쉽게 증명할 수 있다.

 

 이제 모든 x좌표에 대해 비료와 물을 모두 받는 영역의 범위를 구했으니 실제로 이 범위내에서 사각형을 만들 수 있는 경우의 수를 세 보자. count(x, y) = 좌표가 x, y 이하인 영역에서 비료와 물을 모두 받는 좌표의 개수 라고 정의하면, 사각형의 오른쪽 끝점을 (x,y)로 잡았을 때 만들 수 있는 사각형의 개수는 count(x - 1, y - 1)이 된다. 따라서 각각의 x 라인에서 f[x] ~ w[x] 사이의 모든 y에 대해 count(x -1, y -1)을 더해주는 걸 반복하면 답을 구할 수 있다.

 

 이제 이 count 값을 어떻게 하면 빠르게 구할 수 있는지를 생각해보자. 여기서 위에서 언급한 f[x-1] >= f[x] && w[x-1] >= w[x]인 성질을 이용할 수 있다. 맨 왼쪽 라인부터 y 이하 범위에서 count(x -1, y) 전체의 합을 구해서 유지한다고 생각해보자. w[x-1] >= w[x] 이므로 봐야하는 y 라인은 점점 더 아래로만 이동한다. 따라서 각 x좌표에서 답을 계산한 후 count에 계산해야 할 y 라인 범위를 추가해주고, 빼야 하는 값의 갱신을 별도의 배열을 하나 만들어서 기록한다(부분합 응용 개념). 그 다음 x로 이동했을 때 y 라인을 아래로 이동시키며 count 개수에서 빼야하는 것을 계속 빼준다. 이걸 반복하면서 계산하면 전체 시간복잡도 O(N)에 문제를 해결할 수 있다.