주간 PS 리뷰
지난 주에 이것저것 하다보니 (주로 롤이다) 한 주 PS 리뷰를 걸렀다. 2주 동안 좋은 문제를 많이 풀어서 정말 재미있었다. 그동안 명확하게 이해를 못했던 에일리언 트릭에 대해서 심도있게 이해를 하려고 노력했고 성공했다고 생각한다. 도대체 옛날에 잘못 짠 에일리언은 어떻게 맞았는지 1도 모르겠다. 그리고 가장 큰 수확으로 수열과 쿼리 33 (Honorable Mention)을 푼 것이 있겠다. 워낙 좋은 문제라 그런 것도 있고, 첫 루3이라 그런것도 있고, 2트에 맞아서도 매우 기분이 좋다.
Utilitarianism
https://www.acmicpc.net/problem/16191
트리에서 매칭 K개를 고를 때 최대 가중치 합을 구하면 된다. 이런 문제를 접근하는 좋은 방법으로는 MCMF 모델링이 있다. 간단히 트리를 컬러링한 뒤 하얀색에서 검은색으로 가는 용량 1의 방향 간선으로 생각하고 하얀색은 소스에, 검은색은 싱크에 비용 0, 용량 1의 간선으로 연결해주면 플로우를 K번 흘려주는 것이 답이 된다는 사실이 자명하다. 그러나 시간 때문에 MCMF를 실제로 짜는 풀이는 불가능해 보인다. 이 접근이 그럼에도 불구하고 풀이에 의미 있는 이유는 MCMF가 해가 된다는 사실로부터 K에 대한 답의 볼록성을 찾을 수 있기 때문이다. K에 대해 답이 볼록하다면, Alien Trick (wqs binary search ?) 을 사용할 수 있다. 간선 수를 고려하지 않고 최대의 매칭만을 찾는 것은 트리 DP로 O(N)에 간단히 된다. 여기에 +kλ 를 해주는 것은 그냥 모든 간선에 λ를 더하면 끝이다. 모든 Alien에서 다 그렇겠지만 DP에서 같은 답 중 최소 or 최대의 개수가 나오도록 조절하거나 반정수 구간에서 탐색해서 잘 처리하도록 하자. 나는 후자의 방식을 사용했다.
꽃집
https://www.acmicpc.net/problem/17439
prefix sum으로 S[n] = A[1] + ... + A[n]이라 두고 예쁘게 O(N^2) DP식을 세워 보자. D[i][k]를 i번 꽃까지, k개의 묶음으로 나누는 최소 비용으로 정의하면, D[i][k] = min( D[j][k-1] + (S[i]-S[j])(i-j) )가 될 것이다. 여기서 (S[i]-S[j])*(i-j)는 사각부등식을 만족시킨다 (monge array). 이 경우 D[n][k]는 k에 대해 볼록하다. 따라서 역시 Alien을 박고 구간을 쪼갤 때마다 +λ로 식을 바꿔주면 된다. 그럼에도 여전히 식은 제곱의 시간복잡도를 가지는데, 역시 더해지는 항은 monge하므로 monotone queue optimization을 적용해서 풀어주면 된다.
Parklife
https://www.acmicpc.net/problem/17517
구간끼리 겹치지 않고 포함관계 만을 이룬다는 조건을 이용해서 문제를 트리로 바꿀 수 있다. 포레스트가 될 수도 있지만 값이 0인 [0,INF] 구간을 추가하면 하나의 루트로 묶을 수 있다. 문제는 각 K에 대해 루트에서 시작하는 어떤 경로도 V의 원소를 K개 넘게 포함하지 않는 정점 집합 V 중, 값의 합이 가장 큰 것을 구하는 문제로 바뀐다. 이 문제는 슬로프 트릭을 이용해 풀 수 있다. D[u][k]를 u번을 루트로 하는 서브트리에서 리프까지 최대 k개를 선택한 최대값이라고 하자. 우선 u번 정점을 고르는것을 고려하지 않을 때는, 자식 서브트리들의 DP값을 모두 k를 유지시켜 그대로 더하면 된다. 여기서 u번 정점을 고를 경우, k는 1증가하고 값은 u번 정점의 값만큼 증가할 것이다. 이 연산의 결과로는, D[u][k]-D[u][k-1] < A[u]인 모든 A[u][k]들이 D[u][k-1] + A[u]로 바뀌게 된다. 그런데 D[u][k]는 k에 대해 볼록한 함수이므로 특정 지점보다 큰 모든 k에 A[u]를 더하게 되고, 따라서 인접한 두 값 사이의 차이들에 A[u]를 하나 추가한 것이 된다. 따라서 D[u][k]를 관리하는 대신, 항들 사이의 차이를 관리하고, 마지막에 누적합을 해주면 된다. 볼록함수이므로 차이들은 내림차순이 되며 PQ를 이용해 관리한다. 두 서브트리를 합칠 때에는 큰 것부터 짝지어서 합친 뒤 다시 넣어주면 되고, 이때 큰 쪽에 작은 쪽을 합쳐서 로그로 만들어준다. 총 시간복잡도 O(N lg^2 N)에 PQ + 큰-작 으로 상수에 무리없이 풀 수 있다.
싼 비용
https://www.acmicpc.net/problem/1144
칸 사이의 연결에 단조성이나 일반적인 형태 없이 달팽이 모양이나 구멍 등 모든 종류의 답이 다 가능하다. 다항시간의 풀이는 기대하기 힘들 것으로 볼 수 있고, 대신 N, M이 매우 작다. 일반적인 비트DP와 같은 방식으로 왼쪽 위부터 한 칸씩 해당 칸의 선택여부를 고르는 풀이를 시도해보자. 여기서의 문제점은 일반적인 비트 DP로는 연결상태에 대한 정보를 저장할 수 없다는 점이다. 가령 구멍이 뚫린 모양이라면 한 줄, 두 줄만을 상태로서 저장하는 비트DP로는 위에서 연결이 된 상태와 그렇지 않아 추가적인 연결이 필요한 상태를 구분할 수 없다. 이 문제를 해결하는 방법은 각 칸들이 같은 컴포넌트일때를 같은 숫자로 표시해주고, 2진수가 아닌 더 높은 진수를 사용하는 것이다. 여기서의 진수는 인접한 두칸은 무조건 같은 컴포넌트이기 때문에 M<=9이므로 많아봤자 6진수면 충분하다. (선택하지 않은 상태인 0을 포함) 이렇게 하면 2진수일때에 비해 상태공간이 엄청나게 많아질 것 같고 실제로도 그렇다. 그러나 이는 최적화를 하지 않았을 때의 이야기이고 매 DP 업데이트마다 state의 컴포넌트 번호를 앞에 등장하는 것부터 123으로 renumbering해주는 최적화를 하면, 실제 연결관계가 같은 두 상태가 다른 상태로 저장되는 상황을 막을 수 있다. 이 경우의 상태 수를 따져보면, 인접한 두 양수는 같아야 한다는 등의 조건으로 실제로 그렇게 많은 상태가 나오지 않음을 알 수 있다. 이대로 답을 구하면 무난하게 맞을 수 있다. 이런 형태의 DP를 Connection Profile DP라고 부르고 다른 예시 문제로는 BOJ 배관공 김선영 등이 있다.
수열과 쿼리 33
https://www.acmicpc.net/problem/17823
리뷰 안에서 최대한 같이 쓰고 싶었으나 풀이의 크기가 상대적으로 너무 크고 이야기 할 것도 많아서 따로 포스팅을 분리하기로 했다. 빠른 시일내에 올라갈 예정이다.