二次元累積和(cumsum-2d)について
概要
- 二次元で累積和を計算する時、最初に一番上段と、一番左の累積を計算し、それ以外の部分についてもらうdpのイメージで計算することで任意の点の累積和を求めることができる
- 任意の区間での面積を求めるには、いもす法的な発想を用いる
典型例; 値が入っているmatrixが与えられた時、任意の区間での値の和はいくらか
- 概要
- 最初に累積和を計算した変数を持っておき、いもす法ではみ出した部分を引くことで、任意の区間について計算できる
- 問題
from typing import *
import copy
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m = self.m = copy.deepcopy(matrix)
H, W = len(m), len(m[0])
for h in range(1, H):
m[h][0] += m[h-1][0]
for w in range(1, W):
m[0][w] += m[0][w-1]
for h in range(1, H):
for w in range(1, W):
m[h][w] += m[h-1][w] + m[h][w-1] - m[h-1][w-1]
print(*m, sep="\n")
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
h1, w1, h2, w2 = row1, col1, row2, col2
min_h, max_w = min(h1, h2), max(w1, w2)
max_h, min_w = max(h1, h2), min(w1, w2)
tmp = self.m[max_h][max_w]
if min_h > 0:
tmp -= self.m[min_h-1][max_w]
if min_w > 0:
tmp -= self.m[max_h][min_w-1]
if min_h > 0 and min_w > 0:
tmp += self.m[min_h-1][min_w-1]
return tmp
nm = NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]])
print(nm.sumRegion(2, 1, 4, 3)) # 8
print(nm.sumRegion(1, 1, 2, 2)) # 11
print(nm.sumRegion(1, 2, 2, 4)) # 12
pythonのテンプレート
テンプレート1
- 一部の問題でテンプレート1の方法がそのまま通用しなかったり、コーナーケースで失敗するので注意して利用する必要がある
class Cumsum2d:
dp: "Optional[List[List]]" = None
@staticmethod
def generate(h, w, a):
'''da[i][j]:(0,0)~(i,j)の長方形の和'''
Cumsum2d.dp = dp = [[0]*w for j in range(h)]
dp[0][0] = a[0][0]
for i in range(1,w):
dp[0][i] = dp[0][i-1]+a[0][i]
for i in range(1,h):
cnt_w = 0
for j in range(w):
cnt_w += a[i][j]
dp[i][j] = dp[i-1][j]+cnt_w
return dp
@staticmethod
def calc(p, q, x, y):
dp = Cumsum2d.dp
'''da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和'''
if p > x or q > y:
return 0
if p == 0 and q == 0:
return dp[x][y]
if p == 0:
return dp[x][y]-dp[x][q-1]
if q == 0:
return dp[x][y]-dp[p-1][y]
return dp[x][y]-dp[p-1][y]-dp[x][q-1]+dp[p-1][q-1]
テンプレート2
- すこし入力より大きいマトリックスを作成して直接累積和を計算する
G = [[0]*(W+1) for _ in range(H+1)]
for h, w in zip(A, B):
G[h+1][w+1] += 1
for h in range(1, H+1):
for w in range(1, W+1):
G[h][w] += G[h-1][w]
for h in range(1, H+1):
for w in range(1, W+1):
G[h][w] += G[h][w-1]
例; ある範囲以下の最大を求めるような問題の場合、二次元累積和が使用できる
問題
解説
- 面積や大きさを求める問題でないので直感的に結びつかないが、範囲内の最大値を求めるという文脈でいもす法（二次元累積和）が使用できる
解答
N, K = map(int, input().split())
A, B = [], []
for n in range(N):
a,b = map(int, input().split())
A.append(a); B.append(b)
H = max(A + [K]) + 1
W = max(B + [K]) + 1
G = [[0]*(W+1) for _ in range(H+1)]
for h, w in zip(A, B):
G[h+1][w+1] += 1
for h in range(1, H+1):
for w in range(1, W+1):
G[h][w] += G[h-1][w]
for h in range(1, H+1):
for w in range(1, W+1):
G[h][w] += G[h][w-1]
ans = 0
for h in range(H-K):
for w in range(W-K):
tmp = G[h][w] + G[h+K+1][w+K+1] - G[h][w+K+1] - G[h+K+1][w]
ans = max(ans, tmp)
print(ans)
例; チョコレートの切り方を総当りで見つける例
問題
AtCoder Regular Contest 025; B - チョコレート
解答
class Cumsum2d:
dp: "Optional[List[List]]" = None
@staticmethod
def generate(h, w, a):
'''da[i][j]:(0,0)~(i,j)の長方形の和'''
Cumsum2d.dp = dp = [[0]*w for j in range(h)]
dp[0][0] = a[0][0]
for i in range(1,w):
dp[0][i] = dp[0][i-1]+a[0][i]
for i in range(1,h):
cnt_w = 0
for j in range(w):
cnt_w += a[i][j]
dp[i][j] = dp[i-1][j]+cnt_w
return dp
@staticmethod
def calc(p, q, x, y):
dp = Cumsum2d.dp
'''da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和'''
if p > x or q > y:
return 0
if p == 0 and q == 0:
return dp[x][y]
if p == 0:
return dp[x][y]-dp[x][q-1]
if q == 0:
return dp[x][y]-dp[p-1][y]
return dp[x][y]-dp[p-1][y]-dp[x][q-1]+dp[p-1][q-1]
import itertools
H,W=map(int, input().split())
C = [list(map(int, input().split())) for _ in range(H)]
for h,w in itertools.product(range(H), range(W)):
if (h+w)%2==0: # ブラックチョコならば
C[h][w] *= -1 # 正負を反転
Cumsum2d.generate(H,W,C)
ans = 0
for p, q in itertools.product(range(H), range(W)):
for x, y in itertools.product(range(p, H), range(q, W)):
if Cumsum2d.calc(p,q,x,y) == 0:
ans = max(ans, (x-p+1)*(y-q+1))
print(ans)