[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 ...

スクリーンショット 2020-12-30 2.36.54.png

When (w, h) = (1,1)

スクリーンショット 2020-12-30 2.40.56.png

スクリーンショット 2020-12-30 3.22.32.png

(W, h) = (1,2))

スクリーンショット 2020-12-30 2.42.09.png

スクリーンショット 2020-12-30 3.22.56.png

(W, h) = (1,5))

スクリーンショット 2020-12-30 2.44.06.png

スクリーンショット 2020-12-30 3.23.11.png

(W, h) = (2,2))

スクリーンショット 2020-12-30 2.45.37.png

スクリーンショット 2020-12-30 3.23.43.png

(W, h) = (2,3))

スクリーンショット 2020-12-30 2.46.43.png

スクリーンショット 2020-12-30 3.23.58.png

(W, h) = (5,5))

スクリーンショット 2020-12-30 2.48.16.png

スクリーンショット 2020-12-30 3.24.21.png

① 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

[Python] Giga Code 2019 D --Building a house (manipulate with numpy as a matrix !!!) [AtCoder]
Solve AtCoder ABC168 with python (A ~ D)
AtCoder ABC 182 Python (A ~ D)
Solve ABC166 A ~ D with Python
Building a virtual environment with Python 3
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
[Pyenv] Building a python environment with ubuntu 16.04
Building a Python3 environment with Amazon Linux2
Building a Python 3.6 environment with Windows + PowerShell
[AtCoder] Solve ABC1 ~ 100 A problem with Python
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Building a python environment with virtualenv and direnv
Building a Python environment with WLS2 + Anaconda + PyCharm
Debug with VS Code using boost python numpy
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Build a python execution environment with VS Code
Recommendation of building a portable Python environment with conda
Python Ver. To introduce WebPay with a little code.
A note on speeding up Python code with Numba
A memo about building a Django (Python) application with Docker
conda memorandum: Building a Python environment with supercomputer ITO
[Python] How to create a 2D histogram with Matplotlib
Create a 2d CAD file ".dxf" with python [ezdxf]
Can be used with AtCoder! A collection of techniques for drawing short code in Python!
Solve AtCoder 167 with python
Matrix concatenation with Numpy
Hamming code with numpy
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Set up a Python development environment with Visual Studio Code
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Let's create a PRML diagram with Python, Numpy and matplotlib.
[python] A note when trying to use numpy with Cython
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Creating a GUI as easily as possible with python [tkinter edition]
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Build a Python environment with WSL + Pyenv + Jupyter + VS Code
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
[Python] Create a screen for HTTP status code 403/404/500 with Django
Performance comparison between 2D matrix calculation and for with numpy