D - Checker 〜ABC086〜

問題

D - Checker

感想

これがコンテストに出てたら、時間以内に解けなかった気がする。というか、二次元累積和とかいろいろ省略するためにまとめてライブラリ作っておこうかな。

考え

まず、x, yの上限から、x, yについて全探索するのは得策ではないと考える。

そこでx, yに関してKの剰余を考えることで10⁹→10³まで落とし込むことができる。

(0, 0)〜(K - 1, K - 1)の正方形を考えて、(x, y)のKの剰余をそれぞれ(p, q)とすると、以下の関係が成り立っている。

• x / K % 2 == y / K % 2ならば、(x, y)でのB or Wは(p, q)でのB or Wと同じ
• 2での剰余が一致しないときはB or Wが反転する

これで、(x, y)のB or Wパターンを10³まで落とし込むことができました。

最後はこの(0, 0)〜(K - 1, K - 1)の正方形に対して、二次元累積和を求めて最後に模様のパターンを10³ * 10³ * 2だけ全探索して最大値を求めればACとなります。

Accepted Program

#include <iostream>
using namespace std;
#define ll long long

int main () {
  int N, K;
  cin >> N >> K;
  static int white[1000][1000] = {};
  static int black[1000][1000] = {};
  ll x, y;
  char c;     
  for (ll i = 0; i < N; i++) {
    cin >> x >> y >> c;
    if ((x / K) % 2 == (y / K) % 2) {
      if (c == 'W') {
        white[y % K][x % K]++;  
      }         
      else {
        black[y % K][x % K]++;  
      }
    }
    else {
      if (c == 'W') {
        black[y % K][x % K]++;  
      }  
      else {
        white[y % K][x % K]++;  
      }
    }
  }

  // 二次元累積和だと.....?
  int sum_white[1000][1000] = {};
  int sum_black[1000][1000] = {};
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < K; j++) {
      if (i == 0) {
        if (i == 0 && j == 0) {
          sum_white[i][j] = white[i][j];
          sum_black[i][j] = black[i][j];  
        }  
        else {
          sum_white[i][j] = white[i][j] + sum_white[i][j - 1];  
          sum_black[i][j] = black[i][j] + sum_black[i][j - 1];  
        }
      }
      else {
        if (j == 0) {
          sum_white[i][j] = sum_white[i - 1][j] + white[i][j];
          sum_black[i][j] = black[i][j] + sum_black[i - 1][j];  
        }  
        else {
          sum_white[i][j] = sum_white[i - 1][j] + white[i][j] + sum_white[i][j - 1]
                          - sum_white[i - 1][j - 1];  
          sum_black[i][j] = sum_black[i - 1][j] + black[i][j] + sum_black[i][j - 1]
                          - sum_black[i - 1][j - 1];
        }
      }
    }  
  }
  ll ans = 0;
  for (ll i = 0; i < K; i++) {
    for (ll j = 0; j < K; j++) {
      ll sub = sum_white[i][j] + (sum_black[i][K - 1] - sum_black[i][j]);
      sub = sub + (sum_black[K - 1][j] - sum_black[i][j]);
      sub = sub + (sum_white[K - 1][K - 1] - sum_white[K - 1][j] - sum_white[i][K - 1]);
      sub = sub + sum_white[i][j];
      if (ans < sub) {
        ans = sub;  
      }  
    }  
  }
  for (ll i = 0; i < K; i++) {
    for (ll j = 0; j < K; j++) {
      ll sub = sum_black[i][j] + (sum_white[i][K - 1] - sum_white[i][j]);
      sub = sub + (sum_white[K - 1][j] - sum_white[i][j]);
      sub = sub + (sum_black[K - 1][K - 1] - sum_black[K - 1][j] - sum_black[i][K - 1]);
      sub = sub + sum_black[i][j];
      if (ans < sub) {
        ans = sub;  
      }  
    }  
  }
  cout << ans << endl;
}