문제를 정리하면 구해야 하는 것은 max_(i,j){ (q[i] - p[j]) * (e[i] - d[j]) } (q[i]>p[j], e[i]>d[j]) 이다.
q[i0]>q[i1] 이고 e[i0]>e[i1] 인 i0,i1이 있다면, i1은 최적값이 될수 없다. 따라서 제거해도 된다.
마찬가지로 p[j0]<p[j1] 이고 d[j0]<d[j1] 인 j0,j1 이 있다면 j1번째 원소들을 제거해도 된다.
필요 없는 원소들을 실제로 제거하는 것은 q값을 기준으로 스위핑하면서 O(n)에 처리할수 있다.
이렇게 남은 (q[i],e[i]) 들을 q값이 증가하는 순서로 정렬하면 e값은 단조감소한다. (p[j],d[i]) 들도 마찬가지.
그렇다면 A[i,j]=(q[i] - p[j]) * (e[i] - d[j]) 가 total monotonicity 를 갖는 것을 확인할수 있다. 식을 잘 전개해서 정리하면 Monge property 를 만족하는 것을 증명할수 있다.
-
이렇게 쓰고 나면 아주 간단해 보인다. 나도 그렇게 생각했다. 그러나 사소해보이지만 (그래서 다른 블로그 풀이에서는 언급도 잘 안되는..) 중요한 처리가 아직 빠져있었고.. 내 경우에는 이것을 제대로 처리하느라고 하루 이상을 날렸다..
문제가 되는 그 부분은, 지금 A[i,j]의 정의에서는 (q[i]>p[j], e[i]>d[j]) 이 조건이 빠져있었다는 부분이다. 이것을 처리해야 한다.
A[i,j]가 q[i]>p[j], e[i]>d[j] 를 모두 만족할때만 (q[i] - p[j]) * (e[i] - d[j])를 갖고, 나머지 경우에는 -INF를 갖는다고 정의해보자. 이러면 몽주 어레이가 되지는 못한다. 하지만, 여전히 monotone matrix이기는 하다 (..사실 아닌데 그럴거라고 생각했다 ㅜㅜ) 그래서
분할정복 최적화를 적용하는 데에는 문제가 없어야 한다. 하지만 계속 WA를 받았다..
이것이 모노톤하다고 생각한 근거는, i가 주어졌을때 조건을 만족하는 j의 범위를 [l[i], r[i]] 라고 했을때, l[i]와 r[i]가 모두 단조증가한다는 이유였다. 하지만 문제가 된 이유는, l[i]>r[i]인 i가 있을수 있다는 것이었다. 다시 말하면 모든 j에 대해서 -INF값을 갖는 i가 있을 수 있다는 것이다. 이경우에 opt값을 0으로 처리하게 되면 단조성이 깨지게 된다.. (i-1이 j=2에서 최댓값을 갖더라도 찾지 못한다 ㅜㅜ)
그래서 사용한 해결 방법은.. 모든 i들에 대해서 l[i]와 r[i]를 구해서, 조건을 만족하는 j가 존재하는 i값들에 대해서만 최댓값을 구하는 것이었다. l[i]와 r[i]는 모두 단조증가하므로 다행히도 O(n)에 저 범위를 모두 구할수 있었다.
다른 코드에서 본 방법은 좀 더 신기하다.