ABC278 - E - Grid Filling
問題
塗りつぶすことで数$ iがなくなる$ \iffグリッド全体での$ iの個数と塗りつぶした範囲内の$ iの個数が等しい
$ ansを$ Nで初期化する。
$ 1 \leq i \leq Nの$ iについて、ある範囲の$ iの個数がグリッド全体の$ iの個数と一致するか調べ、一致している場合はデクリメントする。
ある(長方形の)範囲に$ iがいくつあるかは二次元累積和でできる。 三次元配列ですべて前計算すると遅いが、$ iごとにその場で作ると間に合う。
code: e.py
def make_acc(k):
R = [0 * (W+1) for _ in range(H+1)] for i in range(1, H+1):
for j in range(1, W+1):
if a != k: continue
for i in range(1, H+1):
for j in range(1, W+1):
return R
def calc(sh, sw, th, tw):
th, tw = th + 1, tw + 1
H, W, N, h, w = map(int, input().split())
for i in range(H):
for j in range(W):
ans = [N * (W-w+1) for _ in range(H-h+1)] for k in range(N):
R = make_acc(k)
for i in range(H-h+1):
for j in range(W-w+1):
c = calc(i, j, i + h - 1, j + w - 1)
for a in ans:
print(*a)