Lamp [AtCoder Beginner Contest 129 D]

https://atcoder.jp/contests/abc129/tasks/abc129_d

解説

https://atcoder.jp/contests/abc129/submissions/5860261

明かりを置くマスを全探索すればいい。
するとこの時点で計算量がO(HW)なので、既にギリギリである。
なのでO(1)かO(logH)とかになる。
明かりを置くマスの上下左右の最近の障害物がわかれば、照らされるマスの個数が分かるので、
それを高速に求めたい。
これは二分探索でできそうだ。
yoko[y] := y行目で障害物があるマスのx座標が入っている
tate[x] := x列目で障害物があるマスのy座標が入っている
どちらにも番兵として、-1とWかHを入れておき、ソートしておく。
これを使うと、二分探索で最近の障害物がlogH, logWで求められる。
これによって、O( H W (logH+logW) ) で計算可能。

int H, W;
string S[2010];
vector<int> yoko[2010];
vector<int> tate[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H >> W;
	rep(y, 0, H) cin >> S[y];

	rep(y, 0, H) yoko[y].push_back(-1);
	rep(x, 0, W) tate[x].push_back(-1);

	rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '#') {
		yoko[y].push_back(x);
		tate[x].push_back(y);
	}

	rep(y, 0, H) yoko[y].push_back(W);
	rep(x, 0, W) tate[x].push_back(H);

	int ans = 0;
	rep(sx, 0, W) rep(sy, 0, H) if (S[sy][sx] == '.') {
		int yoko_idx = lower_bound(all(yoko[sy]), sx) - yoko[sy].begin();
		int L = sx - yoko[sy][yoko_idx - 1] - 1;
		int R = yoko[sy][yoko_idx] - sx - 1;

		int tate_idx = lower_bound(all(tate[sx]), sy) - tate[sx].begin();
		int D = sy - tate[sx][tate_idx - 1] - 1;
		int U = tate[sx][tate_idx] - sy - 1;

		chmax(ans, L + R + D + U + 1);
	}

	cout << ans << endl;
}