[Python] Giga Code 2019 D --Building a house (manipulate with numpy as a matrix !!!) [AtCoder]
2D cumulative sum and numpy
The problem of two-dimensional cumulative sum. However, even if you understand the two-dimensional cumulative sum, if you cannot operate it as a matrix with ** numpy, it will be TLE. .. .. ** ** ** The purpose of this article is to take a closer look and understand what is happening **. ** If you can understand this problem perfectly, the hurdle of numpy should be much lower ... **
** * pypy is an evil way! I want to solve it with python (numpy)! ** **
GigaCode 2019 D-House Construction
For the time being, from the AC code first
AC.py
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W,K,V = LI()
A = np.array([LI() for _ in range(H)])+K
map = np.zeros((H+1,W+1),np.int64)
map[1:,1:] = A
cum_map = map.cumsum(axis=0).cumsum(axis=1)
ans = 0
for h in range(1,H+1):
for w in range(1,W+1):
area = h*w
price = cum_map[h:,w:]+cum_map[:-h,:-w]-cum_map[:-h,w:]-cum_map[h:,:-w]
if np.any(V>=price):
ans = max(ans,area)
print(ans)
The problematic part is here
for h in range(1,H+1):
for w in range(1,W+1):
area = h*w
price = cum_map[h:,w:]+cum_map[:-h,:-w]-cum_map[:-h,w:]-cum_map[h:,:-w]
I'm doing something like cum_map [: -h,: -w]! !! !!
For the time being, let's see the actual movement with input example 3 ...
When (w, h) = (1,1)
(W, h) = (1,2))
(W, h) = (1,5))
(W, h) = (2,2))
(W, h) = (2,3))
(W, h) = (5,5))
① and ② are point symmetric: cum_map [h :, w:] + cum_map [: -h,: -w]
③ and ④ are point symmetric: -cum_map [: -h, w:]-cum_map [h :,: -w]
** I feel like I understand the atmosphere! ** **
end!
Recommended Posts