DPL_3_A: Largest Square (続き)

1日寝かせてダメだったら解説読む

ダメだった
ていうか考える時間とMPが不足していた
星2.5個だし何か思いついてもいいかなあとは思ったんだけど

どれどれ

まず考えられるのが、すべての正方形について、その内部に1が含まれないかを調べるアルゴリズムです。

それがダメなのはわかってた

dp[i][j]にタイル(i,j)から左上に向かってできる最大の正方形の辺の長さ（タイルの数）を記録していきます。

それもダメだと思ってた
え、それでいいの？
上と左からわかる？

dp[i][j]の値はその左上、上、左の要素の中で最も小さい値に1を加えたものになります。

左上も使うのか・・・
ヒントの絵を真に受けすぎた
素直すぎるんだな（そうしておこう
左上を使うと知ってても上の関係を見つけられてたかというと微妙

ほんとかな
書き書き
たしかに
左上の正方形の右と下に1列追加するって考えるとわかりやすい

わかってしまえば書くのは難しくなさそう
こうかな

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

def largest_square(h, w, c):
    ls = 0
    dp = [[None] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if c[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = (
                    min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                )
            ls = max(ls, dp[i][j] ** 2)
    return ls

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

main()

AC
番兵置いた方がキレイかな？

解答例のコード 
なにやってるんだここ？

  dp[i][j] = (G[i][j] + 1) % 2
  maxWidth |= dp[i][j]

Gの0と1を入れ替えてdpに代入している
dp[i][j]の最大値を求めている
そういうことね

G[i][j]が0か1しかないからそうなるわけか・・・
これじゃダメですか

  dp[i][j] = 1 - G[i][j] 
  maxWidth = max(maxWidth, dp[i][j])

|=は確かに速そうだけど1を足して2で割った余りっていうのは
あんまり速そうな気がしないなあ
1から引くくらいならそっちの方が速くない？
なんか間違えたかな？