【Python】GigaCode 2019 D - 家の建設(numpyで行列のまま操作！！！)【AtCoder】

2次元累積和とnumpy

2次元累積和の問題。
ただし2次元累積和については理解していても、numpyで行列のまま操作できないとTLEになる。。。
何が起こっているのだろうか、じっくり眺めて理解することがこの記事の目的。
この問題が完璧に理解できたら、numpyのハードルもずっと下がるはず・・・

※pypyは邪道！python(numpy)で解きたい！

GigaCode 2019 D - 家の建設

とりあえず、先にACコードから

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)

問題の箇所はココ

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]

cum_map[:-h,:-w]とかなにしてるのー！！！
とりあえず入力例3で実際の動きを眺めてみる・・・

(w,h)=(1,1)の時

(w,h)=(1,2)の時)

(w,h)=(1,5)の時)

(w,h)=(2,2)の時)

(w,h)=(2,3)の時)

(w,h)=(5,5)の時)

①と②が点対称：cum_map[h:,w:]+cum_map[:-h,:-w]
③と④が点対称：-cum_map[:-h,w:]-cum_map[h:,:-w]

雰囲気理解したような気がする！

おわり！