ABC 086 D - Checker
まず1次元で考えてみる。
マスが1列に並んでいて、$ Kマスごとに黒と白で交互に塗り分けられているとする。このとき、左端から$ Kマスの色分けを決めれば、残りのマスの色も決まることが分かる。たとえば$ x_q \quad (0 \le q \lt K)が白なら、$ x_i（ただし整数$ p\gt0について $ i = 2pK + q）は白になるし、$ x_i（ただし整数$ p\ge0について $ i = (2p + 1)K + q）は黒になる。
また、その$ Kマスの塗り分けの場合の数はつぎのように$ 2K通りであることが分かる。
https://gyazo.com/d0e2c5c98d1a84ecbc6aa45b2dcad637
ここで$ (x_i, c_i)（$ c_iは$ Wか$ B）という情報が$ N個与えられたとすると、つぎの手順で最大でいくつの情報が正解にできるか求められる。まず各$ 0\le q\lt Kについて、$ x_qのマスが白だったときに、$ (x_i, c_i)が正しくなる数（$ C_q）と間違う数（$ I_q）を求めておく。そうすると$ x_qが黒になったときに正解数がいくつ増減するかは$ \Delta_q = I_q - C_q\quad(0\le q \lt K)で計算しておくことができる。そして、最初の$ Kマスの塗り分けの$ 2K通りに応じて正解数を増減させ最大値を調べればよい。
実際、最初$ Kマスがすべて白なら正解数は$ C = \sum_q C_qになる。次に左端の1マスを黒にすると正解数の増減は$ \Delta_0、つぎに左端の2マスを黒にするとさらに$ \Delta_1、そのまま $ \Delta_{K-1}まで増えたあと、$ -\Delta_0、$ -\Delta_1と増減する。したがって、累積和$ S_k = \sum_i \Delta_iをあらかじめ計算しておけば、答えは$ \max(\max_k (C + S_k), \max_k (C + S_{K-1} - S_k))で求まる。$ O(N + K)で計算できることがわかる。
2次元でも同様にして左下の$ K \times Kマスそれぞれを黒に塗ったときの正解数の増減$ \Delta (i, j)\quad(0\le i\lt K, 0\le j\lt K)を求めておき、それの2次元累積和を使って左下の$ K\times Kマスの塗り分けに応じて正解数がいくつになるか調べればよい。
注意点としては、単純に原点の位置$ (x, y)を$ 0\le x \lt K, 0\le y \lt Kの範囲で動かすだけでなく、黒白を反転した場合も調べる必要があることである。この探索は$ O(2K^2)なので計算量は$ O(N + 2K^2) = O(2\cdot10^6)になる。
https://gyazo.com/7576c08b7a9ddced37b106a8c01365ba
この黒白の反転を見落としていて最後通せなかった。無念。
code:java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
int count = 0;
int[][] delta = new intKK; for (int i = 0; i < N; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
char c = scanner.next().charAt(0);
int p = x / K + y / K;
if ((p % 2 == 0 && c == 'W') || (p % 2 == 1 && c == 'B')) {
count++;
}
}
for (int i = 0; i < K; i++) for (int j = 1; j < K; j++) deltaij += deltaij - 1; for (int j = 0; j < K; j++) for (int i = 1; i < K; i++) deltaij += deltai - 1j; int max = count;
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= K; j++) {
if (i > 0) {
}
if (j > 0) {
}
if (i > 0 && j > 0) {
}
max = Math.max(max, c1);
max = Math.max(max, c2);
}
}
System.out.println(max);
}
}