codeforces 1060C Maximum Subrectangle

알고리즘 문제/math

gaelim 2018. 12. 13. 14:52

문제 정의

각각의 길이 n, m 인 1차원 배열 a, b를 서로 곱해서 2차원 배열을 만든다.

행렬곱의 결과 c(i,j) = a(i) * b(j) 이다.

이때 c에서 가장 큰 사각형의 넓이를 구하시오. 단, c(i,j)의 합이 수 k 를 넘지 않아야한다.

a와 b의 길이는 각 각 최대 2,000 사이즈이다.

1<= ai, bi <=2e3 이며,주어지는 1<= k는 2* 1e9 이하이다.

문제 해결

경우의 수를 현명하게 구하면 계산가능하다.

배열의 형태는 다음과 같다.

Matrix C is

[ a0b0 a0b1 a0b2 a0b3 a0b4 .... a0b(n-1) ]

[ a1b0 a1b1 a1b2 a1b3 a1b4 ... a1b(n-1) ]

[ a2b0 a2b1 ....... a2b(n-1) ]

.....

[ a(n-1)b0 .... a(n-1)b(n-1)]

이 떄 C 위에 생성할 수 있는 모든 사각형은

start from (ai, bj) width (n-j+1) height (n-i+1) 이다.

그러면 경우의 수는 2000 * 2000 * SUM(2000~1) * SUM(2000~1) 일 것이다.

그리고 그 펼쳐진 사각형들 안의 엘리먼트들을 더하는 연산 SUM(2000~1) * SUM(2000~1)을 수행해야하므로

모든 연산시간은 2000* 2000* (SUM(2000~1)^4) 이 될것이다.

굉장히 고통스러운 시간이므로 현명하게 찾아야한다.

일단 사각형 ( (a0 * b0) , (an * bm) ) 까지의 모든 합은 다음과 같다.

SUM (a(0~n)) * SUM ( b(0~m) )

여기서 한가지 착안점은 a와 b에 대한 각각의 presum array를 구하고, 사용하면 C 위 에서 펼쳐지는 임의의 사각형의 값에 대해 단 O(1)만에 값을 구할 수 있다.

그렇지만 여전히 (ai, bj) 를 지칭하고 높이와 너비를 지정하는데에는 2000* 2000* SUM(1~2000) * SUM(1~2000) 의 경우의수가 존재한다. 여전히 고통스러운 시간이다.

이 때, 각각의 presum array 위에서 구간 길이 요소만을 구한다면 시간을 줄일 수 있다.

a는 row를 결정짓는 요소이므로 row[] 란 배열에 다음의 정보를ㄴ ㅓㅎ으면된다

presum A[i] = {0, a[0], a[0]+a[1] , a[0]+a[1]+a[2], .... };

for (int i=1; i<=a.lengh; i++)
{
for (int j =1; j<=i; j++)
{

row[i-j] = min ( row[i-j], presum_A[i]-presum_A[i-j] );

}
}

이렇게 하면 i까지 도달하는 모든 가능한 길이 j 에 대해 row [j]는 최소화가 될것이다.

또한 b에 대해서도 이렇게 작업을 하고 나면, row[i] * col[j] <= k 를 만족하는 가장 큰 i*j를 구하기만 하면된다.