ARC 089 D - Checker - ykmakuのブログ

問題

解法

まず $(x,y)$ と $(x+2K,y),\ (x,y+2K)$ の色は一致するので入力の $x,y$ を $x \% 2K,y\%2k$ としていいです.

黒色の正方形の左下をどこにするかで平面の色の塗り方は決まります.
塗り方の周期性から黒色の正方形の左下の座標の候補は $[0,2K)\times[0,2K)$ としていいです.

したがって $4K^2$ 個の塗り方全てに対して叶えられる希望の個数を数えてそれのmaxを取れば良いです.
累積和を使うと1つの塗り方に対して叶えられる希望の個数を $O(1)$ の計算量時間で求めることができます.

感想

解説には全ての色をBにできると書いてあったが気が付かなかった...
累積和もパッと書けるようになりたい

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,k;
	cin>>n>>k;
	int grid[2][4000][4000]={0};
	for(int i = 0; i < n; i++){
		int x,y;
		char c;
		cin>>x>>y>>c;
		x%=2*k;
		y%=2*k;
		if(c=='B'){
			grid[0][x][y]++;
			grid[0][x+2*k][y]++;
			grid[0][x][y+2*k]++;
			grid[0][x+2*k][y+2*k]++;
		}else{
			grid[1][x][y]++;
			grid[1][x+2*k][y]++;
			grid[1][x][y+2*k]++;
			grid[1][x+2*k][y+2*k]++;
		}
	}
	int sum[2][4000][4000]={0};
	for(int color = 0; color < 2; color++){
		for(int i = 0; i < 4*k; i++){
			for(int j = 0; j < 4*k; j++){
				sum[color][i][j] = (j==0?0:sum[color][i][j-1]) + grid[color][i][j];
			}
		}
		for(int i = 1; i < 4*k; i++){
			for(int j = 0; j < 4*k; j++){
				sum[color][i][j] += sum[color][i-1][j];
			}
		}
	}

	int ans = 0;
	for(int i = 0; i < 2*k; i++){
		for(int j = 0; j < 2*k; j++){
			int res = sum[0][i+k][j+k] - sum[0][i][j+k] - sum[0][i+k][j] + sum[0][i][j];
			res += sum[1][i+k][j+2*k] - sum[1][i][j+2*k] - sum[1][i+k][j+k] + sum[1][i][j+k];
			res += sum[1][i+2*k][j+k] - sum[1][i+2*k][j] - sum[1][i+k][j+k] + sum[1][i+k][j];
			res += sum[0][i+2*k][j+2*k] - sum[0][i+2*k][j+k] - sum[0][i+k][j+2*k] + sum[0][i+k][j+k];
			ans = max(ans,res);
		}
	}

	cout << ans << endl;

	return 0;
}