DPL_3_B: Largest Rectangle (続き)

やっぱりわかりませんでした
解説を見る

全探索のアルゴリズムでは時間内に答えを求めることはできません。

そうでしょうね

正方形を探すために用いたアルゴリズムも適用することができないため、別の方法を考える必要があります。

想定の範囲内

まず

各要素について上に向かってキレイなタイルが何個連続しているかをテーブルTに記録します。

これがヒストグラムの正体
これは簡単なDP

そのヒストグラムを左から見ていきながら
(長方形の高さ, 左端)をスタックに入れたり出したりしていく
高さが低くなれば長方形の右端が来たということ
右端に来たところで長方形の面積が確定

って
DPはヒストグラム作るだけか
後半はDPじゃないよな
ヒストグラム作るだけなら簡単だ
思考の星が多いのはともかくとして実装の星が多いのは後半かな
場合分け多いし

ざっくり理解でなるほどねくらいになったところで書いてみる
AC出せたのがこんなコード

def read_tiles(h, w):
    c = []
    for _ in range(h):
        c.append([int(x) for x in input().split()])
    return c

def make_histogram(h, w, c):
    hg = [[None] * w for _ in range(h)]
    for j in range(w):
        hg[0][j] = 1 if c[0][j] == 0 else 0
    for i in range(1, h):
        for j in range(w):
            hg[i][j] = hg[i - 1][j] + 1 if c[i][j] == 0 else 0
    return hg

def largest_rectangle(h, w, c):
    lr = 0
    hg = make_histogram(h, w, c)
    s = []
    for i in range(h):
        hg[i] += [0]
        for j in range(w + 1):
            if len(s) == 0:
                if hg[i][j] > 0:
                    s.append((hg[i][j], j))
            else:
                top = s[-1]
                if top[0] < hg[i][j]:
                    s.append((hg[i][j], j))
                elif hg[i][j] == top[0]:
                    pass
                else:
                    top = s.pop()
                    while True:
                        lr = max(lr, top[0] * (j - top[1]))
                        if len(s) == 0 or s[-1][0] < hg[i][j]:
                            break
                        top = s.pop()
                    s.append((hg[i][j], top[1]))
    return lr

def main():
    h, w = map(int, input().split())
    c = read_tiles(h, w)
    print(largest_rectangle(h, w, c))

main()

インデントが深すぎて死にそう
スタックからpopするのか、一番上を見るだけにするのかちょっと悩ましかった
解説と見比べると考え方は合ってるっぽいけど
サンプルコードの方はスタックの見方が違っててforのループで書けてる

                    top = s.pop()
                    while True:
                        lr = max(lr, top[0] * (j - top[1]))
                        if len(s) == 0 or s[-1][0] < hg[i][j]:
                            break
                        top = s.pop()
                    s.append((hg[i][j], top[1]))

は

                    while len(s) > 0 and s[-1][0] >= hg[i][j]:
                        top = s.pop()
                        lr = max(lr, top[0] * (j - top[1]))
                    s.append((hg[i][j], top[1]))

でいいのか
どうもこういうところうまく書けないなあ
なんとかなりそうな気はしてたんだけど

for j in range(w + 1):のループにあたるところを関数に抜き出してあって
インデントが減ってる
これはまあいいとしよう