けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #614 (Div. 1) A. NEKO's Maze Game (R1400)

いくらなんでも 2 分で解ける問題とは思えないのですが...

問題へのリンク

問題概要

2 × N のグリッドが与えられる。最初はグリッドのマスはすべて「通路」の状態であって、マス (1, 1) からマス (2, N) に到達することができる。以下の q 個のクエリに答えよ。

  •  i 回目のクエリは (r, c) で与えられ、その時点でもしマス (r, c) が「通路」ならば「壁」になり、「壁」ならば「通路」となる。
  • その処理を行った後で、(1, 1) から (2, N) へ到達できるかどうかを判定せよ

制約

  •  1 \le N \le 10^{5}

考えたこと

これそんなに簡単なの!?
通り抜けられる条件は、以下の条件を満たすことと同値である (0-indexed に直している)

  • 任意の (r, c) に対して、以下のすべてが成立する:
    • (r, c) と (1-r, c-1) のどちらかは通路である
    • (r, c) と (1-r, c) のどちらかは通路である
    • (r, c) と (1-r, c+1) のどちらかは通路である

そこで、この条件の違反している部分の個数を常に更新することで、クエリに答えることができる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<vector<int> > turo(2, vector<int>(N, 1));
    int dame = 0;
    for (int q = 0; q < Q; ++q) {
        int r, c; cin >> r >> c; --r, --c;
        // 新たに壁に
        if (turo[r][c]) {
            for (int dc = -1; dc <= 1; ++dc) {
                int nc = c + dc;
                if (nc < 0 || nc >= N) continue;
                if (!turo[1-r][nc]) ++dame;
            }
            turo[r][c] = false;
        }
        // 壁を消す
        else {
            for (int dc = -1; dc <= 1; ++dc) {
                int nc = c + dc;
                if (nc < 0 || nc >= N) continue;
                if (!turo[1-r][nc]) --dame;
            }
            turo[r][c] = true;
        }
        if (!dame) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}