IOI 2010 Day 1 Task 3 : Quality Of Living

dovelet 링크

R*C 크기의 격자가 있고, 이 격자에 각각 숫자가 있다(1부터 (R*C)까지 unique하게).

이제 여기서 H*W 크기의 임의의 직사각형을 잡으면, 그 안에 있는 숫자들의 median(중간값)을 구할 수 있다.

그러면 약 (R-H+1)*(C-W+1) 가지의 직사각형이 나오고 각각의 median이 나오겠지?

그 중 최댓값을 구하는 문제이다.

(1≤H≤R≤3000, 1≤W≤C≤3000)

새로운 수가 들어왔다 나갔다 하면서 Median이 계속 변하는 문제는 O(lgN)만에 새로운 값을 추가하고, O(1)만에 중간값을 알아내고, O(1)만에 값을 삭제할 수 있다.

그래서 이 문제의 경우, H*W 크기의 격자를 전체 격자 위에서 ㄹ자 모양으로 움직이도록 밀면 모든 경우의 median을 따질 수 있겠다... 하는 생각이 들었다. ('sliding window'라고 부르는 것 같다)

이 경우 시간복잡도는 한 번 움직일 때마다 O(max(H,W)lg(H*W)) 만큼의 시간이 들고, 결국 N=max(R,C)라고 하면 O(N·lgN)의 시간이 들게 된다.

이를 최대 N^2번 하므로 시간복잡도는 O(N^3·lgN)이 된다. 끔찍하다(...)

물론 H*W가 클 수록 median 검사 횟수는 줄어들겠지만, 그래도 시간 제한에 걸릴 확률이 충분히 크다.

이 문제는 결국 최적화 문제로 생각할 수 있다. median을 최대한으로 만들어봐라...

그럼 최적화 문제에서는 어떤게 쓰일까? '일반적인' 방법으로는 역시 parametric search가 있겠지.

어떤 값에 대해서 parametric search를 돌릴 것인가에 대해서는 사실 문제에 힌트로 주어져 있다.(...)

The median quality rank among an odd number of quality ranks is defined to be the quality rank m in the set such that the number of quality ranks better than m equals the number of quality ranks worse than m.

어떤 수들의 median이라는 것은, 자신보다 작은 수의 갯수와 자신보다 큰 수의 갯수가 일치한다는 것이다.

그런데, 어떤 H*W 영역에서 자신보다 작은 수의 갯수보다 자신보다 큰 수의 갯수가 많다면? 혹은 적다면?

그림을 통해, 자신보다 작은 수와 큰 수의 갯수를 통해 자신보다 작은, 혹은 큰 median이 존재하는지를 간단하게 알 수 있다.

f(n) = (median이 n이하인 구역이 존재하는가?) 라고 하면

while(l+1 != r){
    mid = (l+r)/2;
    if(f(mid)) r=mid;
    else l=mid;
}

간단한 코드로 parametric search를 수행할 수 있으며, 이에 걸리는 시간은 log(R*C)≒7 정도이다.

그러면 f(n)의 시간복잡도는 최대 n^2 일텐데, 이부분에서 굉장히 고민했는데 생각보다 간단하다.

각 칸에 있는 수가 n 이하이면 1, n 초과이면 0을 적은 2차원 배열과,

그 반대로 n 이상이면 1, n 미만이면 0을 적은 2차원 배열 두 개를 만든다.

그러면 그 값들은 n이 일정하면 변하지 않으므로 prefix sum을 이용한 구간 합 O(1)만에 구하기처럼,

임의의 구역의 합을 O(1)만에 구할 수 있게 된다.

여기까지 시간복잡도는 O(N^2)이다.

이후 각 구간을 돌면서, 각 구간 안의 두 배열의 숫자들의 합을 비교해주면 된다.