AOJ DPL_3_B Largest Rectangle

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    T = [il() for _ in range(H)]
    dp = [[0] * W for _ in range(H)]

    ret = 0
    # ヒストグラムの作成
    for h in range(H):
        for w in range(W):
            if T[h][w] == 0:
                dp[h][w] = max(1, dp[h - 1][w] + 1)

        stack = []
        # 長方形の最大面積計算
        for w in range(W):
            position = -1
            while len(stack) > 0 and stack[-1][0] > dp[h][w]:
                height, position = stack.pop()
                ret = max(ret, height * (w-position))

            if len(stack) == 0 or (len(stack) > 0 and stack[-1][0] < dp[h][w]):
                position = w if position == -1 else position
                stack.append((dp[h][w], position))

        for height, position in stack:
            ret = max(ret, height * (W - position))
    print(ret)


if __name__ == '__main__':
    main()

考え方

螺旋本より、動的計画法の問題。
初めに、各h(0 <= h <= H)を１行ずつ、動的計画法で縦の高さを求める。
この高さと、高さが存在する列から長方形の面積を求める。

---

まず、高さについて。
１行ずつタイルを確認し、汚れていない場合にはmax(1,１行上のタイル + 1)として、
汚れていないタイルの縦に積みあがった最大値を求める。

次に、横幅について。
高さと、その高さがどの列に存在するかをスタックに積んでおく。
スタックからデータを順に取り出すと、高さと高さが存在する列の情報から面積を求めることができる。
さらにスタックからデータを順に取り出していくと、高さが高い列から低い列へ向かって、データを取り出すことが出来る。
つまり、先に取り出されるデータの方が高さを持っているため、あとから取り出されるデータは、
一番初めに取り出されたデータの列までは横幅を持つことが出来る。

例えば、(高さ, 列) とした時、
スタック = [(1, 0), (2, 1), (4, 2), (7, 3)]のデータを一つずつ取り出すと
1つ目のデータ(7, 3)は高さ7, 横幅1で面積7
2つ目のデータは、自身の存在する列と、自分より高い(7, 3)の列を使用することが出来るため
高さ4, 横幅2で面積8
3つ目のデータは、自身の存在する列と、自分より高い(7, 3),(4, 2)の列を使用することができるため
高さ2, 横幅3で面積6 ... と、各列の取りうる最大面積を求めることができる。