ARC081 F : Flip and Rectangles(700)
作成日：2017.08.28
最終更新日：2017.08.28
問題概要
$H \times W$のマス目で各マスが黒または白に塗られているものがある。
操作「任意の行または列を選び、そこに含まれるマスの白黒を入れ替える」を好きな回数だけ行う。
その後マス目に沿った長方形で、そこに含まれるすべてのマスが黒で塗られているものを1つ選ぶ。
この時、操作を適切に行うことで選ぶことができる最大の長方形の面積を求めよ。
制約
$2 \leq H,W \leq 2000$
$|S_i| = W$
$S_i$は'#'(黒を表す)もしくは'.'(白を表す)のみからなる
$S_i$の$j$文字目は上から$i$番目、左から$j$番目のマスの色を表す
考え方
ある1行に含まれるすべてのマスを黒で塗れることは、白で塗られていたその行のマスを含む列に対して操作を1回ずつ行うことで達成できることからすぐに分かる。
よって行と列の対称性から答えは少なくとも$max(H,W)$であることが分かる。
次に2行にわたるマス目を黒に塗られた状態にできるかを考える。
まず1列目を黒にするためには、1列目が白で塗られている行を選んで操作する必要がある。
その操作の後に行に対して操作を行うことは、1列目のマス目すべてが黒である状態でなくなるので意味をなさない。
よって2列目以降も黒にするためには、列に対しての操作だけで黒にできる必要がある。
その条件は1列目における1,2行目のマスの色が同じであるかどうかと注目している列における1,2行目のマスの色が同じであるかどうかが一致していることである。
これは1列目と比較する代わりに直前の列と比較しても同じである。
選ぶ長方形が3行以上にわたる場合も、隣り合う2行について同様に考えることができる。
それによって、$2 \times 2$のマス目において行のマスの色が同じであるかが一致しているものが$A \times B$の長方形の範囲で選べる時には、
問題の条件を満たす$(A+1) \times (B+1)$の長方形を選ぶことができることが分かる。
この最大値を求める時に、行数を決めてから列数を最大にとることを愚直にやるとTLEするので工夫する。
異なる行数のものを同時に調べるために、条件を満たす$2 \times 2$のマス目が上から下に向かって何個重なって続いているかの数を並べてそれを各行について見ていく。
すると、多くの行でつながっているものはより少ない行でつながっているともみなせるから、ある数以上のものが何個横に並んでいるかをその数が小さいものから大きいものの順にstackで積んでいけば考えられる。
こうすることで計算量は$O(HW)$となるから間に合う。
ソースコード
マクロ等はこちら
int H,W;
char S[2010][2010];
int x[2010];
int ans;
int main(){
scanf("%d%d" , &H , &W);
repp(i,0,H){
scanf(" %s" , S[i]);
}
ans = max(W,H);
repp(i,1,H){
stack<P2> v;
v.push(MP(0,0));
repp(j,1,W){
if(1 ^ (S[i-1][j] == S[i][j]) ^ (S[i-1][j-1] == S[i][j-1])){
++x[j];
} else {
x[j] = 0;
}
int p = v.top().first;
int q = v.top().second;
int r = 0;
while(p > x[j]){
r += q;
ans = max(ans , (p+1) * (r+1));
v.pop();
p = v.top().first;
q = v.top().second;
}
if(p < x[j]){
v.push(MP(x[j],1+r));
} else {
v.top().second += 1+r;
}
}
int r = 0;
while(!v.empty()){
int p = v.top().first;
int q = v.top().second;
r += q;
ans = max(ans , (p+1) * (r+1));
v.pop();
}
}
printf("%d\n" , ans);
return 0;
}解法まとめ
$2 \times 2$のマス目においてすべて黒にできる条件を満たすことのできるものが縦に何個つながっているか$(x_i)$を各行について求める。
そしてstackを用いてその行を下端とする条件を満たす長方形について最大となる面積を調べる。(12-45行)
答えは$max(H,W)$以上であることに注意する。(11行)