ARC 089 D - Checker (500) - kurarrr's memooo

問題

問題概要

N個の点(xi,yi)と色(B|W),自然数Kが与えられる.
幅Kの市松模様で,(xi,yi)を与えらえれた色にするという希望を最大何個満たすことができるか.
1 <= N <= 10⁵, 1 <= K <= 10³, 0 <= xi,yi <= 10⁹

解法

全てのマスに対して,(x,y)の色C(x,y)は,C(x,y) = C(x+2K,y) = C(x,y+2K)なので,
x,y %= 2Kとして 0 <= x,y < 2Kで考えて良い.
また,C(x,y) != C(x+K,y)であるから,C(x,y)=W <-> C(x+K,y)=B より,
全てC(x,y)をBにできるか,と言い換えることができる.

市松模様の黒正方形の左下を決めてやると模様を確定させることができるので,
黒正方形の左下(xs,ys) (0<=x<=2K-1,0<=y<=K-1)を全て試せば全パターンが試せる.
矩形領域内の総和は二次元累積和を使うと前処理O(K²),クエリO(1)で出せるのでO(N+K²)で十分間に合う.

解説と解説放送では別の方法を提示していた.
解説はimos法で,左下(xs,ys)としてK*Kの領域を取った時(xi,yi)が入るような正方形区間,
すなわち xi-K+1<=xs<=xi, yi-K+1<=ys<=yi と xi+1<=xs<=xi+2K,yi+1<=ys<=yi+2K に全て+1する.(後半の領域はmod2Kをとるとxi,yiと重なる)
全てのマスに+1していたのでは間に合わないのでimos法を使わないとだめ.
なお,0<=x,y<=2K-1でははみ出してしまうので,0<=x,y<=4K-1でやっといて,
0<=x,y<=2K-1からはみ出しているx,yにはS[x%2K][y%2K] += S[x][y] とする.

解説放送の方法ではシンプルに
S[x][y] = sum(0<=i<=x, 0<=j<=y) (a[i][j])とすると
sum(x1<=x<=x2, y1<=y<=y2)(a[x][y]) = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]
で求められることを用いてxs,ysを左下にした時の5つの黒正方形領域の和を求めている.
なお前処理としてS[x][y]を求めるのは
S[x][y] = a[x][y] + S[x-1][y] + S[x][y-1] - S[x-1][y-1] で求められる.
(横に足していって縦に足していってもOK)

コードでは条件分岐させたくないのでx,yを+1して,a[0][y] = a[x][0] = 0としている.
本来は0<=x<=2K-1,0<=y<=K-1だが,(x,y)を黒にした時k個条件を満たすならば, (x,y)を白左下にすればN-k個条件を満たすことを用いて,0<=x,y<=K-1で済んでいる.

メモ

実装で色々ミスして間に合わなかった.
二次元累積和 -> 区間内の和を求める
imos法 -> 区間に値を足す
というのが実は区別がついていなかったので色々為になった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 2003;

int N,K,c[MAX_N][MAX_N],s[MAX_N][MAX_N];

void prepare(){
  REP(x,1,2*K+2)
    REP(y,1,2*K+2) s[x][y] = c[x][y] + s[x-1][y] + s[x][y-1] - s[x-1][y-1];
}

int query(int x1,int y1,int x2,int y2){
  // return sum(x1<=x<=x2,y1<=y<=y2)
  if(x1>x2||y1>y2) return 0;
  else return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> K;
  fill(c[0],c[MAX_N-1],0);
  rep(i,N){
    int x,y; char cc;
    cin >> x >> y >> cc;
    if(cc=='B') x += K;
    x %= (2*K); y %= (2*K);
    c[x+1][y+1]++;
  }
  prepare();
  int ans = -INF;
  REP(x,1,K+1) REP(y,1,K+1){
    int temp = query(x,y,x+K-1,y+K-1) + query(x+K,y+K,2*K,2*K) + query(1,1,x-1,y-1)
               + query(x+K,1,2*K,y-1) + query(1,y+K,x-1,2*K);
    ans = max(ans,max(temp,N-temp));
  }
  cout << ans << endl;
  return 0;
}