ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • codeforces 1060C Maximum Subrectangle
    알고리즘 문제/math 2018. 12. 13. 14:52

    codeforces 1060C Maximum Subrectangle


    문제보러가기

    https://codeforces.com/contest/1060/problem/C


    문제 정의

    각각의 길이 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를 구하기만 하면된다.





    '알고리즘 문제 > math' 카테고리의 다른 글

    삼각형의 면적 구하기, 백준 2166 다각형의 면적  (0) 2019.03.20
    백준 1081 합  (0) 2019.03.09
    codeforces 1060C Maximum Subrectangle  (0) 2018.12.13
    908C New Year and Curling  (0) 2017.12.31
    900B Position in Fraction  (0) 2017.12.15
    878A : Short Program  (0) 2017.10.27

    댓글 0

Designed by Tistory.