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

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

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


#[GigaCode 2019 D - 家の建設]( https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_d)

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

```python: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で実際の動きを眺めてみる・・・

![スクリーンショット 2020-12-30 2.36.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/4860c856-cd4b-f575-3249-2c39eb6f99fe.png)

## (w,h)=(1,1)の時
![スクリーンショット 2020-12-30 2.40.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/467050a5-b261-7c6c-cfe0-e5c05de5842e.png)

![スクリーンショット 2020-12-30 3.22.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/655661dd-90d7-191e-beb4-09bba51cca62.png)


## (w,h)=(1,2)の時)
![スクリーンショット 2020-12-30 2.42.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/f1b93868-d236-cc7d-2338-67308843941d.png)

![スクリーンショット 2020-12-30 3.22.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/d51afb31-2af8-4381-f2ff-66f3c99b44b0.png)


## (w,h)=(1,5)の時)
![スクリーンショット 2020-12-30 2.44.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/3baa5bb1-4309-700e-b5b4-b2e1a8fcf7a7.png)

![スクリーンショット 2020-12-30 3.23.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/36d0f0a1-3b21-e068-ea08-205dfddc58b0.png)


## (w,h)=(2,2)の時)
![スクリーンショット 2020-12-30 2.45.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/8c10599b-153d-cc27-f18e-8b79570beab4.png)

![スクリーンショット 2020-12-30 3.23.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/16191934-8bb9-7c26-66a7-a5e2c7056235.png)


## (w,h)=(2,3)の時)
![スクリーンショット 2020-12-30 2.46.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/1be52fca-38fc-5dac-53c1-4bf03304786e.png)

![スクリーンショット 2020-12-30 3.23.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/1f8726c5-2457-4ee8-f033-44a32827fbba.png)


## (w,h)=(5,5)の時)
![スクリーンショット 2020-12-30 2.48.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/98eee419-6689-3bc0-2d34-5b6e827a0a52.png)

![スクリーンショット 2020-12-30 3.24.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/785975/ac4fc4a1-b951-d5a0-39b8-8d5079f693f4.png)

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

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

おわり！