SRM 610 div1 easy TheMatrix

考えたこと

この間のARC080Fとか最大長方形とかを思い出す
制約を見たらh,w<=100と小さいので愚直にO((HW)^2)ができそう
二次元累積和っぽく実装したら通った
かなり簡単目だったのかO((HW)^2)が嘘解法だったのか…？

解法

(x, y)を左上、(w-1, h-1)を右下とする各長方形について、条件を満たす長方形を求めていく。
dp[i][j] = (x, y)を左上、(i, j)を右下とする長方形で条件が成り立つかどうかとすると、
dp[i][j]は

• dp[i][j] = true (dp[i-1][j] == true && dp[i][j-1] == true && board[i][j] != board[i-1][j] && board[i][j] != board[i][j-1])
• dp[i][j] = false (otherwise)

となるので順番に求めていく。