| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 365 | 185 | 102 | 60.000% |
You are given an $N \times M$ matrix $A$. You are also given a special kernel of size $K \times K$, and a stride $S$. Your task is to implement a convolution-like operation using a kernel with unique properties. The kernel must always remain completely within the matrix boundaries during its operation.
Specifically, the unique features of a kernel in this problem are:
For example, the following is the kernel when the size is $3$ and $5$, respectively.
\[\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}\]
The stride determines the step size for moving the kernel across the matrix. The kernel moves across the matrix based on the given stride. At each valid position (where the kernel fits entirely within the matrix boundaries), the element-wise sum of the matrix elements covered by the kernel is calculated.
Calculate a new matrix $B$ containing the sums from all valid kernel positions. The size of $B$ should be $\left(\frac{N-K}{S}+1\right) \times \left(\frac{M-K}{S}+1\right)$.
The first line contains four space-separated integers: $N$ and $M$, denoting the size of the image; $ K$, denoting the kernel size; and $S$, denoting the stride. ($1 \le N,M \le 2\,000;$ $1 \le K, S \le \min\{N,M\};$ $K \equiv 1 \pmod 2;$ $S$ is a divisor of $\gcd(N-K,M-K)$)
The following $N$ lines of input contain $NM$ integers, where each line has $M$ space-separated integers, denoting the value of the matrix $A$. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10^6 \le A_{ij} \le 10^6$)
Output $\left(\frac{N-K}{S}+1\right)$ lines denoting the resulting matrix $B$ after applying the kernel with the given stride.
Each line should contain $\left(\frac{M-K}{S}+1\right)$ space-separated integers. The $j$-th integer of the $i$-th line should represent $B_{ij}$.
Modified constraints apply: $1 \le N,M \le 30$.
Modified constraints apply: $1 \le N,M \le 300;$ $S=1$.
Modified constraints apply: $1 \le N,M \le 2\,000;$ $S=1$.
Original constraints apply: $1 \le N,M \le 2\,000$.
5 5 3 1 1 2 3 4 5 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4
28 31 34 33 30 27 18 15 12
For the given input, the kernel size is $3$, and the stride is $1$. The initialized kernel is:
\[\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}.\]
The kernel moves with a stride of $1$, and only valid positions where the kernel is fully within the matrix are considered. At each position, the sum of the overlapping matrix elements is calculated.
For example, when the upper left corner of the kernel is placed at $A_{11}$, the value $B_{11}$ is:
\[\begin{bmatrix} 1 & \mathbf{\color{red}2} & 3 \\ \mathbf{\color{red}5} & \mathbf{\color{red}6} & \mathbf{\color{red}7} \\ 9 & \mathbf{\color{red}8} & 7 \end{bmatrix} \rightarrow 2+5+6+7+8=28.\]
5 5 3 2 1 2 3 4 5 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4
28 34 18 12
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 기말고사 코딩 테스트 2번