ARC 081 F - Flip and Rectangles
問題概要
0,1が書かれているh*wの盤面がある.
行または列を全て反転する操作が何回でもできるとして,
その中の要素が全て1であるような長方形の最大の面積を求めよ.
解法
ここの方法がわかりやすかったのでこれでやった.
ex.
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
まず横方向にxorをとっていく.
a[i][j]
1 1 1 1
1 1 1 0
1 1 0 0
0 1 0 0
その a[i][j] を縦方向に見ていって, その部分列を要素が{0,0,...,0}か{1,1,...,1}であるように取ることができるなら
横に一つ伸ばして, jとj+1のその部分列で長方形を作ることができる.
例えば,赤色の部分を取ると
a[i][j]
1 1 1 1
1 1 1 0
1 1 0 0
0 1 0 0
この部分が長方形にできることがわかる.
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
よって hist[i][j] = (a[i][j]と等しい数が上に何個続くか) とすると,
hist[i][j]
1 1 1 1
2 2 2 1
3 3 1 1
1 1 2 2
これを横方向にヒストグラムと見なし,ヒストグラムの最大長方形を求めれば良い.
上の青い部分を取れば,
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
の部分で最大長方形が作れることがわかる.
ただし, (長方形) = (高さ) * (幅+1) としてやることに注意する.
メモ
解けなかった.
flipなどでは特に階差xorを考えるのと,
最大長方形のアルゴリズム覚えておきたい..
