E - Grid Filling

[hxrxchang]

https://atcoder.jp/contests/abc278/tasks/abc278_e

問題概要

gridに対して、h * w の長方形を左上から順に置いていく。置くとそこに書かれていた数字は見えなくなる。それをはみ出さずに置けるところすべてに対して試す。 置いた各ステップにおいて、見える数字の種類は何種類あるか求めよ。

解き方

初期状態で各数字がいくつ出現するかを覚えておく。 長方形を移動していくときに、隠れる数字と再度出現する数字が分かるので、出現回数を増減させることで、種類数が分かる。 計算量は 縦方向の移動 * (縦方向の移動で隠れる数字と再度出現する数字の計算 + 横方向の移動) * 横方向の移動で隠れる数字と再度出現する数字の計算

で、O(N ** 3)

H, W, N, H2, W2 = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(H)]

count = [0] * (N + 1)
num_of_kinds = 0

def count_kinds(count):
    result = 0
    for i in range(1, N + 1):
        if count[i] > 0:
            result += 1
    return result

for i in range(H):
    for j in range(W):
        n = A[i][j]
        if count[n] == 0:
            num_of_kinds += 1
        count[n] += 1

for h in range(H - H2 + 1):
    ans = []
    count2 = count[:]

    for i in range(h, h + H2):
        for j in range(W2):
            count2[A[i][j]] -= 1

    ans.append(count_kinds(count2))

    for w in range(1, W - W2 + 1):
        for i in range(h, h + H2):
            count2[A[i][w - 1]] += 1
            count2[A[i][w + W2 - 1]] -= 1
        ans.append(count_kinds(count2))

    print(*ans)

https://atcoder.jp/contests/abc278/submissions/52763955