문제

아이디어

N * M 크기의 직사각형의 I행 J열 칸을 포함하는 부분 직사각형은 I * J * (N-I+1) * (M-J+1)개가 된다.
이 공식을 적용해 각 칸을 포함하는 부분 직사각형의 개수를 쉽게 구할 수 있고, 이를 통해 정답을 구해낼 수 있다.

문제를 자세히 읽지 않는다면 오해하기 쉽다.
입력으로 주어진 표를 이용한다면 터무니없이 작은 결과가 나온다.
입력으로 주어진 표를 2 * 2 사이즈로 확장하여 풀어야 올바른 결과가 나온다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static char[][] rect;
    static long[] ans = new long[26];
    static long[][] rectNum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        rect = new char[n * 2][m * 2];
        rectNum = new long[n * 2][m * 2];
        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            for (int j = 0; j < m; j++) {
                char c = temp.charAt(j);
                rect[i][j] = rect[i + n][j] = rect[i][j + m] = rect[i + n][j + m] = c;
            }
        }

        for (int i = 0; i < n * 2; i++) {
            for (int j = 0; j < m * 2; j++) {
                rectNum[i][j] = (long) (i + 1) * (j + 1) * (n * 2L - i) * (m * 2L - j);
            }
        }

        for (int i = 0; i < n * 2; i++) {
            for (int j = 0; j < m * 2; j++) {
                ans[rect[i][j] - 'A'] += rectNum[i][j];
            }
        }

        for (long num : ans) {
            System.out.println(num);
        }
    }
}

채점 결과

스트릭이 어느새 1년을 넘었다!