codeforces #578 div2 D - White Lines ( 배열구간 연산 )

https://codeforces.com/contest/1200/problem/D

 

W,B 둘중 하나로만 이루어진 n*n배열이 주어졌을 때, 단 한번 k*k크기의 구간을 W로 바꿀 수 있다면 W로 빙고가 이루어지는 경우의 최대값을 반환하는 문제이다.

 

 

row따로 column따로 생각할 건데, row만 차례로 볼 때, i번째 row에서 B가 나타난다면 첫번째 위치를 L, 마지막 위치를 R이라고 하자. 이때, R-L+1<=k인 경우에 그 줄은 W로 빙고가 이루어질 수 있다. 이때 가능한 모든 i,j가 속한 구간을 [r1,c1] ~ (r2+1,c2+1) 이라고 하자(반개구간, 0base이기 때문에 반개구간 사용하는 편이 편하다.)

 

최종적으론 ac[i][j] => (i,j)를 기준으로 k*k 구간을 W로 바꿀때 추가되는 빙고의 수라고 할 것이다.

 

일단은 row와 column 따로따로 '[r1,c1] ~ (r2+1,c2+1)에 속하는 ac[i][j]의 값을 1 증가하라' 는 의미로 다음과 같이 전처리 한다.

 

ac[r2 + 1][c2 + 1]++; //[0,0] ~ (r2+1, c2+1)에 속하는 ac[i][j]의 값을 1 '증가'시킬 것이다.

ac[r1][c1]++;   //[0,0] ~ (r1, c1)에 속하는 ac[i][j]의 값을 1 '증가'시킬 것이다.
ac[r1][c2 + 1]--;  //[0,0] ~ (r1, c2+1)에 속하는 ac[i][j]의 값을 1 '감소'시킬 것이다. 
ac[r2 + 1][c1]--; //[0,0] ~ (r2+1, c1)에 속하는 ac[i][j]의 값을 1 '감소'시킬 것이다. 

 

두 번의 전처리가 모두 끝나면 ac에 저장된 값을 prefix sum 해주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int MAX = 2001;

string v[MAX];
int n, k, ac[MAX][MAX] = { 0 }, ans = 0;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
		cin >> v[i];

	for (int i = 0; i < n; i++) {
		int L = n, R = -1;
		for (int j = 0; j < n; j++) {
			if (v[i][j] == 'B') {
				L = min(L, j);
				R = max(R, j);
			}
		}
		int r1 = max(0, i - k + 1);
		int r2 = i;
		int c1, c2;
		//조건에 맞으면(r1,c1) ~ (c1,c2)는 모두 1씩 증가
		if (L == n && R == -1) ans++;
		else {
			if (R - L + 1 <= k) {
				c1 = max(0, R - k + 1);
				c2 = L;
				ac[r1][c1]++;
				ac[r2 + 1][c2 + 1]++;
				ac[r1][c2 + 1]--;
				ac[r2 + 1][c1]--;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		int L = n, R = -1;
		for (int j = 0; j < n; j++) {
			if (v[j][i] == 'B') {
				L = min(L, j);
				R = max(R, j);
			}
		}
		int c1 = max(0, i - k + 1);
		int c2 = i;
		int r1, r2;
		//조건에 맞으면(r1,c1) ~ (c1,c2)는 모두 1씩 증가
		if (L == n && R == -1) ans++;
		else {
			if (R - L + 1 <= k) {
				r1 = max(0, R - k + 1);
				r2 = L;
				ac[r1][c1]++;
				ac[r2 + 1][c2 + 1]++;
				ac[r1][c2 + 1]--;
				ac[r2 + 1][c1]--;
			}
		}
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++)
			cout << ac[i][j] << " ";
		cout << '\n';
	}
	cout << '\n';

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i > 0) ac[i][j] += ac[i - 1][j];
			if (j > 0) ac[i][j] += ac[i][j - 1];
			if (i > 0 and j > 0) ac[i][j] -= ac[i - 1][j - 1];
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++)
			cout << ac[i][j] << " ";
		cout << '\n';
	}

	int t = 0;
	for (int i = 0; i + k - 1 < n; i++)
		for (int j = 0; j + k - 1 < n; j++)
			t = max(t, ac[i][j]);

	cout << ans + t << '\n';
}