#1286 부분 직사각형(구현)

이번 문제는 Gold IV 난이도 문제네요.  N개의 줄에 M개의 글자가 각자 써져 있는 문자들을, 3번 복사를 해서 2N개의 줄에 2M개의 글자가 써져 있는 문자들로 만든 다음, 직사각형을 선택해서 부분 문자열들을 만드는 작업을 할 때, 모든 부분 직사각형에 나타나는 문자들의 빈도를 계산하라는 문제입니다.  예를 들어서

 

ABCD

EFGH

 

라는 2줄에 걸쳐 각각 4글자씩의 문자열이 주어졌다면, 3번 복사를 해서

 

ABCDABCD

EFGHEFGH

ABCDABCD

EFGHEFGH

 

를 만들고, 직사각형을 선택해서 필요한 부분문자열을 만듭니다.  예를 들어서 왼쪽위가 (1, 1), 오른쪽 아래가 (3, 2) 직사각형이 있다면,

 

ABCDABCD

EFGHEFGH

ABCDABCD

EFGHEFGH

 

가 선택되어서, F 글자의 빈도가 하나 늘고, G 글자의 빈도가 하나 늘게 되겠죠.

 

Sub Rectangle

 

https://www.acmicpc.net/problem/1286

1286번: 부분 직사각형

기본적으로 이 문제는 크게 어렵지 않은데, 숫자어림을 잘못해서 틀렸습니다를 한번 받았습니다.  최대 50줄, 최대 50글자.  모든 문자가 하나의 문자로만 이루어진 경우, 총 문자는 2,500자.  대충 \( 25^{4} \cdot 50^{2} = 976,562,500 \) 으로 int 범위를 벗어나지 않을거라고 생각했는데, 3번 복사를 하니까, 숫자가 훨씬 커지게 됩니다.  즉, 특이한 경우에 int 범위를 벗어납니다.

 

알고리즘은 기본적으로 k번째 문자가 몇번이나 나타날것인가를 따집니다.

k번째 문자

위와 같이 1차원적으로 생각한다음 2차원으로 확장하면 되므로, 1차원에서 K번째 문자가 몇번 나타날것인가를 따집니다.

k번째 문자가 포함되기 위해서는 반드시 k번째 문자 왼쪽에서 시작해서 오른쪽에서 끝나는 범위를 가져야 합니다.  N개의 문자를 가지고 있고, 인덱스가 1부터 시작하는 문자열이라면, K번째 문자를 포함하는 경우의 수는 \(K (N-K+1)\)이 됩니다.  2차원적으로는 단순하게 곱하기만 늘어날 뿐 똑같습니다.  (r, c) 인덱스의 문자이고, n*m 문자열에 대해서 \( (r+1)(n-r)(c+1)(m-c) \)의 빈도가 됩니다.

 

복사를 했으니까, 그것만 적절하게 처리하면 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1286 - Partial Rectangle
//    - by Aubrey Choi
//    - created at 2020-01-14
//----------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, m, i, j, t, r; char s[52]; static long long h[26];
  scanf("%d%d",&n,&m);
  for(i=0;i<n;i++)
  {
    t=(i+1)*(2*n-i)+(i+n+1)*(n-i);
    scanf("%s",s);
    for(j=0;j<m;j++)
    {
      r=(j+1)*(2*m-j)+(j+m+1)*(m-j);
      h[s[j]-'A']+=t*r;
    }
  }
  for(i=0;i<26;i++) printf("%lld\n", h[i]);
}