品質管理 [パソコン甲子園2015 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0320?year=2015

考察仮定

1. 差分を考えていく問題であるが、差分だけを再計算することで判定できないか考える
2. 現在の状態を打ち消して、更新して、現在の状態を考えなおすという典型テクを使う
3. 計算量的にもその方針で大丈夫そう

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0320/judge/3140775/C++14

check(x,y) := 頂点(x,y)と対応する上下左右対称の座標の値が全て同じか
を用意する。
xの左右対称のx座標はN-1-xであり、yの上下対称のy座標はN-1-yである。
全ての値をチェックして、同じなら1（true）を返す。
　
N*Nだけ頂点があるが、対称の頂点を1つにまとめると、N*N/4頂点になる。
ok := 上下左右対称の頂点の個数
0≦x＜N/2, 0≦y＜Nの頂点をチェックして、okを事前に計算する。
これでok=N*N/2であれば、初期盤面は上下左右対称ということになるので、答えを+1しておく。
　
差分を計算する場合は、座標のスワップをする前にその座標だけチェックをして全て同じであればokを-1する（現在の状態の打ち消し）。
座標をスワップする（更新）。
その後に、その座標だけチェックをして全て同じであればokを+1する（現在の状態を考え直す）。
差分1つの計算が終わったらまた、ok=N*N/4をチェックして、答えを+1するか決める。

int C, N, P[1010][1010];
int ok;
//---------------------------------------------------------------------------------------------------
int check(int x, int y) {
    if (P[y][x] == P[N - 1 - y][x] and P[y][x] == P[N - 1 - y][N - 1 - x] and P[y][x] == P[y][N - 1 - x]) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> C >> N;
    rep(y, 0, N) {
        string s; cin >> s;
        rep(x, 0, N) P[y][x] = s[x] - '0';
    }

    rep(y, 0, N / 2) rep(x, 0, N / 2) if (check(x, y)) ok++;
    
    int ans = 0;
    if (ok == N * N / 4) ans++;
    rep(c, 0, C - 1) {
        int D; cin >> D;
        rep(d, 0, D) {
            int r, c; cin >> r >> c;
            r--; c--;

            if (check(c, r)) ok--;
            
            P[r][c] = 1 - P[r][c];

            if (check(c, r)) ok++;
        }
        if (ok == N * N / 4) ans++;
    }
    cout << ans << endl;
}