AtCoder Regular Contest 081: F - Flip and Rectangles
解けず。
意識するようにしたい: <blockquote class="twitter-tweet" data-lang="en"><p lang="ja" dir="ltr">なんか詰まった時にとりあえず試すといいやつがあって、
・累積和をとる
・階差をとる
・階差xor(?)(隣り合う項のxor)をとる
あたりは結構重要だなあとなる(例えば区間に一様に加算するときは累積和をとると変更箇所が2箇所になって扱いやすいし、今回のFも階差xorで解ける)</p>— らて (@LatteMalta) August 20, 2017</blockquote>
solution
$O(HW)$。
長方形の左上$(l_x, l_y)$と左下$(l_x, r_y)$を固定してできるだけ右に伸ばすことを考える。 好きな行のマスの反転ができるので、各行$y$で点$(l_x, l_y)$の色を左上に揃えるように反転させる。 各列の各点でそれより右で最初に色の切り替わる点を求めておいて区間minクエリで求まる。 ただしその区間$[l_y, r_y]$でのminが全て一致していた場合は、その次の列を反転させることで長方形を伸ばせてしまう。
ここまでだと$O(H^2W)$だが、次の$2$点を使えば$O(HW)$。
- 長方形をこれ以上伸ばせない点を一発で得るには、各行の色の変化でなくて、隣接する行ごとの不一致に注目する
- 区間minクエリを$O(H^2)$回発行するのでなくて、ヒストグラム中の面積を求めるようなstackを使ったテクで$O(H)$
implementation
#include <iostream>
#include <stack>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
// input
int h, w; cin >> h >> w;
vector<string> s(h);
repeat (y, h) cin >> s[y];
// solve
auto hist = vectors(h - 1, w, int());
repeat (y, h - 1) {
hist[y][w - 1] = 1;
repeat_reverse (x, w - 1) {
bool p = ((s[y][x] == s[y + 1][x]) == (s[y][x + 1] == s[y + 1][x + 1]));
hist[y][x] = (p ? hist[y][x + 1] + 1 : 1);
}
}
int result = w;
repeat (x, w - 1) {
stack<pair<int, int> > stk;
repeat (i, (h - 1) + 1) {
int h_i = (i < h - 1 ? hist[i][x] : 0);
int j = i;
while (not stk.empty() and stk.top().second > h_i) {
int h_j; tie(j, h_j) = stk.top();
stk.pop();
setmax(result, h_j * (i - j + 1));
}
if (stk.empty() or stk.top().second < h_i) {
stk.emplace(j, h_i);
}
}
}
// output
printf("%d\n", result);
return 0;
}