2888번: KRALJEVI

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

$O(rc * \lg {rc})$

같은 사람끼리의 최소 거리를 구하는 방법을 알아내면 이 방법을 M, S에 대해 적용하면 된다.
한 말로부터 각 위치까지의 최소 거리를 표시해보자. 지정한 말을 지나는 기울기 1, -1의 직선에 대해 대칭성을 볼 수 있다.
이를 착안하여 동일한 각 말들의 좌표 (x,y)를 (x-y,x+y)로 바꿔 표시해보자.
말들간의 최소 거리는 x,y 좌표 차이 합이 된다.
문제는 같은 사람의 모든 말들 쌍의 좌표 차이 합을 구하는 문제가 된다.
이를 구하기 위해 각 말들의 x좌표를 정렬해보자. (xi에서 o<=i<n)
xi-x(i-1) = ai라 하자.
x 좌표간 차이 합에 포함된 ai의 수는 i*(n-i)개 이다.
즉 x 좌표간 차이 합은 i*(n-i)*ai의 합이 된다.
이를 y좌표간에 마찬가지로 적용하여 구하고자 하는 답을 구할 수 있다.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 1e3;
int r, c, x[MAX_N*MAX_N], y[MAX_N*MAX_N], cnt;
char str[MAX_N][MAX_N];
ll f(char ch) {
    ll res = 0;
    cnt = 0;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (str[i][j] == ch) x[cnt] = i - j, y[cnt++] = i + j;
    sort(x, x + cnt);
    sort(y, y + cnt);
    for (int i = 1; i < cnt; i++)
        res += (ll)i*(cnt - i)*(x[i] - x[i - 1] + y[i] - y[i - 1]);
    return res / 2;
}
int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++) scanf("%s", str[i]);
    printf("%lld %lld", f('M'), f('S'));
    return 0;
}