2018-07-23

2018 codeFlyer 本選 F - 配信パズル (800 点)

クエリ処理問題差分更新 XOR 二次元グリッド操作 Yes/No判定問題条件の言い換えパリティ不変量 AtCoder unrated公式コン AtCoder800点操作:flip 盤面を予め変更する

本番中なんとか解けたけど、すごくグチャグチャしたん。

問題概要

すぬけ君は、 $Q$ 日間にわたって、毎日次のようなパズルを解こうとしている。

すぬけ君の持っている端末に、縦 $H$ 行、横 $W$ 列からなる格子状の盤面が毎日配信されてくる。それぞれのマスは白または黒で塗られている。ただし、 $i+1$ 日目の盤面は、 $i$ 日目に配信される盤面の上から $r_i$ 行目で左から $c_i$ 列目のマスの白黒が反転したものである。

$Q$ 個分の盤面に対し、

はじめに最大 1 回、長方形領域を指定してその領域内の白黒を反転
好きな回数だけ、好きな行か列を選んで白黒を反転することを繰り返す

という操作を行い、すべての盤面を白にすることができるかどうかを判定せよ。

制約

$1 \le H, W\le 2000$
$1 \le Q \le 300000$

解法

いかにも「日々の盤面変化が小さいこと」を利用しそうな問題である。

まず、最初の「最大 1 回長方形領域を指定する」がなかった場合を考える。まず、行や列を選んで白黒反転させる操作は

盤面内のどの 2 × 2 の正方形内の白の個数の偶奇を変えない

ということがわかる。逆に少し考えると、どの 2 × 2 の正方形内を見ても白の個数が偶数であるならば、全部白にできることが少し考えるとわかる。そこでこの問題を、

盤面を 2 × 2 の正方形すべてについて「白の個数」の偶奇をとったもの

の世界で考えることにする。このとき、この変換した世界において

毎日ごとの $(r_i, c_i)$ の反転はどうなるか
「長方形領域で反転」はどうなるか

を考える。前者はマス $(r_i, c_i)$ を含む正方形は 4 個あるので、その 4 個の偶奇を変えればよい。後者は

長方形状の 4 点の偶奇を変える
x 座標または y 座標の等しい 2 点の偶奇を変える
1 点の偶奇を変える

のいずれかになることを示せる。こうすると、与えられた盤面を「長方形領域反転」によって全部偶数にできるかどうかを判定することができる。

実装状は「奇数のマス」を常に set で管理するようにした。奇数のマスが 5 個以上だったらそもそも "NO" で、4 個以下のときはそれが「長方形状の 4 点」「x 座標または y 座標が等しい 2 点」「1 点」「0 点」のいずれかであれば "YES" になる。計算量は

最初の盤面変換 $O(HW\log{(HW)})$
クエリ $O(Q\log{(HW)})$

という感じになる。

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 2100;
int ori[MAX][MAX];
int fi[MAX][MAX];
typedef pair<int,int> pint;

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  memset(ori, 0, sizeof(ori));
  memset(fi, 0, sizeof(fi));
  for (int i = 0; i < N; ++i) {
    string str; cin >> str;
    for (int j = 0; j < str.size(); ++j) {
      if (str[j] == '#') ori[i][j] = 1;
    }
  }
  int num = 0;
  set<pint> se;
  for (int i = 0; i < max(N-1, 1); ++i) {
    for (int j = 0; j < max(M-1, 1); ++j) {
      int con = 0;
      for (int i2 = 0; i2 < 2; ++i2) {
        for (int j2 = 0; j2 < 2; ++j2) {
          if (ori[i+i2][j+j2] == 1) ++con;
        }
      }
      fi[i][j] = con % 2;
      if (fi[i][j]) {
        ++num;
        se.insert(pint(i, j));
      }
    }
  }
  
  for (int q = 0; q < Q; ++q) {
    if (se.size() <= 1) cout << "Yes" << endl;
    else if (se.size() == 2) {
      vector<pint> v;
      for (auto it = se.begin(); it != se.end(); ++it) v.push_back(*it);
      if (v[0].first == v[1].first) cout << "Yes" << endl;
      else if (v[0].second == v[1].second) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
    else if (se.size() == 3) cout << "No" << endl;
    else if (se.size() == 4) {
      vector<pint> v;
      for (auto it = se.begin(); it != se.end(); ++it) v.push_back(*it);
      sort(v.begin(), v.end());
      if (v[1].first != v[0].first) cout << "No" << endl;
      else if (v[2].first == v[0].first) cout << "No" << endl;
      else if (v[3].first != v[2].first) cout << "No" << endl;
      else if (v[1].second == v[0].second) cout << "No" << endl;
      else if (v[2].second != v[0].second) cout << "No" << endl;
      else if (v[3].second != v[1].second) cout << "No" << endl;
      else cout << "Yes" << endl;
    }
    else cout << "No" << endl;
    
    if (q == Q-1) break;
    int x, y;
    cin >> x >> y;
    --x, --y;
    for (int xx = max(x-1, 0); xx <= x; ++xx) {
      for (int yy = max(y-1, 0); yy <= y; ++yy) {
        if (xx >= max(N-1, 1)) continue;
        if (yy >= max(M-1, 1)) continue;
        if (fi[xx][yy] == 0) ++num, se.insert(pint(xx, yy));
        else --num, se.erase(pint(xx, yy));
        fi[xx][yy] = 1 - fi[xx][yy];
      }
    }
  } 
}