ARC089 D : Checker(500)
作成日：2018.01.23
最終更新日：2018.01.23
問題概要
二次元平面上の一辺が$1$のマスを一辺が$K$の市松模様で塗る。
マス$(x_i , y_i)$を黒[$B$](白[$W$])で塗るという$N$個の条件のうち同時に満たすことができる最大の個数を求めよ。
制約
$1 \leq N \leq 10^5$
$1 \leq K \leq 10^3$
$0 \leq x_i , y_i \leq 10^9$
$i \neq j$ならば$(x_i,y_i) \neq (x_j,y_j)$
$c_i$は$B$または$W$
考え方
市松模様は$x$,$y$いずれの方向に見ても$2K$周期である。
よって塗り方として$(2K \times 2K)$通り試せば十分である。
また座標はすべて$mod \: 2K$で考えれば良いことも分かる。
これを愚直に行うと$O(NK^2)$となり間に合わないので工夫する。
塗り方を決めるごとに、黒(白)となる範囲に与えられた条件がいくつ入るかを高速に求められれば良い。
これは座標を$mod \: 2K$で考えていることから、累積和を用いることで達成できる。
この時の全体の計算量は$O(K^2)$となるので十分である。
ちなみに$y$軸方向に$K$だけずれると色が必ず変わることから、白で塗る条件を黒で塗る条件に変えることで実装量を減らすことができる。
ソースコード
マクロ等はこちら
int N,K;
int b[2002][2002];
int s[4002][4002];
int get(int x , int y){
return s[x+K-1][y+K-1] + s[x-1][y-1] - s[x-1][y+K-1] - s[x+K-1][y-1];
}
int main(){
cin >> N >> K;
repp(i,0,N){
int x,y;
char c;
cin >> x >> y >> c;
if(c=='W') y += K;
++b[x%(2*K)+1][y%(2*K)+1];
}
repp(i,1,4*K+1){
repp(j,1,4*K+1){
s[i][j] = s[i][j-1] + b[(i-1)%(2*K)+1][(j-1)%(2*K)+1];
}
}
repp(j,1,4*K+1){
repp(i,1,4*K+1){
s[i][j] += s[i-1][j];
}
}
int ans = 0;
repp(i,1,2*K+1){
repp(j,1,2*K+1){
ans = max(ans , get(i,j) + get(i+K,j+K));
}
}
cout << ans << endl;
return 0;
}解法まとめ
白に塗る条件は$y$軸方向に座標を$K$だけずらすことで黒に塗る条件に変えることができる。(15行)
座標をすべて$2K$で割った余りで置き換え、条件の個数の累積和を取る。(18-27行)
$2K \times 2K$通りの市松模様の塗り方それぞれにおいて満たすことができる条件をこの累積和を用いて求める。
それらの最大値が答えである。(28-34行)