JOI難易度６ Mall

問題原文

https://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf

問題要旨

× のグリッドで表現される広い土地がある。
各土地の値段は であり、その１セルの土地の価格を表す。ただし、−１であれば人が住んでいることを表す。
この土地のうち、 × の区画を買収するとして、その最小価格はいくらになるか？ただし、人が住んでいるような土地は買収できない。

• 
• 
• 与えられる入力では、必ずどこかの土地が買収できる

解法

二次元累積和で、ある区画を買収した場合の価格を高速に求める。
人がいるような地点については、想定しうる答えの上界以上の値にすることで、事実上無視することができる。
今回の場合は最大に広い土地、かつ最高の値段なので、1000 × 1000 × 100 = 10⁸ が上界になる。
必ずどこかの土地が買収できることが制約で決められているので、 -1 を 10⁸ に置き換えて計算しても問題ない。（価値が負の土地はないので、人がいるような土地の価値を計算しても、必ず答えの上界以上の値になる）

実装

W, H = map(int, input().split())
SECTION_W, SECTION_H = map(int, input().split())
G = [list(map(int, input().split())) for i in range(H)]
ANS_UPPER_BOUND = 10 ** 8  # 1000 * 1000 * 100

for h in range(H):
    for w in range(W):
        if G[h][w] == -1:
            G[h][w] = ANS_UPPER_BOUND

# 二次元累積和をとる
for h in range(H):
    for w in range(W):
        if (h > 0) and (w > 0):
            G[h][w] += (G[h - 1][w] + G[h][w - 1] - G[h - 1][w - 1])

        elif (h > 0) and (w == 0):
            G[h][w] += G[h - 1][w]

        elif (h == 0) and (w > 0):
            G[h][w] += G[0][w - 1]

ans = ANS_UPPER_BOUND
for h in range(SECTION_H - 1, H):
    for w in range(SECTION_W - 1, W):
        section_cost = 0
        section_cost += G[h][w]

        dh, dw = h - SECTION_H, w - SECTION_W
        if dh >= 0:
            section_cost -= G[dh][w]

        if dw >= 0:
            section_cost -= G[h][dw]

        if (dh >= 0) and (dw >= 0):
            section_cost += G[dh][dw]

        ans = min(ans, section_cost)

print(ans)

感想

気晴らしにJOIをはじめた。
実装力を鍛えていくぞ！