Codeforces Round #641 (Div. 1 C / Div 2. E) Kamil and Making a Stream

問題: Problem - E - Codeforces

公式解説: Codeforces Round #641 Editorial - Codeforces

問題概要

$n \times m (1 \leq n, \mathit{m} \leq 1000)$ の行列 $A$ が与えられる。$i$ 行 $j$ 列の要素は $a_{i, j}$ であり，0 なら白，1 なら黒である。

この行列のすべての要素に対して，以下の操作を行う。

上下左右に同じ色が存在しない要素の色はそのままにする
上下左右のいずれかに同じ色が存在する要素の色を反転する

この操作について，次の $t (\leq 10^5)$ 個のクエリに答えよ。

すべての要素に対して操作を$p$ 回繰り返した後の $i$ 行 $j$ 列の要素の色を答えよ。

解法概要

今回の問題では，色がそのままになる条件が厳しく，色が変わる条件は緩い。条件に従って Sample 3 なんかを手でやってみると，操作を行っても色が変わらないエリアと操作ごとに色が変わるエリアがあると考えたときに，色が変わるエリアが徐々に広がる。

操作前	1回目の操作後	2回目の操作後
01011 10110 01101 11010 10101	01000 10000 00001 00010 00101	11111 11111 11111 11110 11101

3回目の操作後	4回目の操作後	5回目の操作後
00000 00000 00000 00000 00001	11111 11111 11111 11111 11111	00000 00000 00000 00000 00000

もう少し詳しく見てみると，「隣に同じ色の要素がある (= 次の操作で色が変わる)」要素との最短距離に応じて，色が変わらない状態→色が毎回変化する状態へと変化するタイミングが決まることがわかる。

数学的帰納法っぽく証明してみる。

隣に同じ色がある要素との最短距離が 0 ，つまり自分の隣に自分と同じ色があるような要素の場合はあと 0 回で毎回色が変化する状態」になる。つまりもうすでに色が毎回変化する状態になっている。

また，隣に同じ色がある要素との最短距離が $d$ の要素 $a_{i, j}$があり，$d$ 回の操作後に毎回色が変化するようになると仮定する。さらに，その要素の隣の要素に，隣に同じ色がある要素との最短距離が $d+1$ の要素 $a_{i', j'}$があったとする。

$d$ 回の操作後，$a_{i, j}$ はまだ色は変化していないが， $d+1$ 回目の操作後から毎回色が変化する，つまり4近傍に色が同じ色要素が存在する状態になっている。一方，$a_{i', j'}$ はまだ色が変化しておらず，まだ4近傍に同じ色の要素がないので $d+1$ 回目の操作後も色が変化しない。 (仮定より，$a_{i, j} \neq a_{i', j'}$ が必ず成り立っている)

したがって，「隣に同じ色の要素がある」要素との最短距離が「その要素が後何回の操作で色が毎回変化する状態になるか」である。

クエリの数より，クエリの度に「隣に同じ色の要素がある」要素からの距離を求めていては間に合わない。また，「隣に同じ色の要素がある」要素は最大 $10^6$ 個あるので，BFS を $10^6$ 回やって距離の最小値を取るわけにもいかない。

しかしこの場合は，「隣に同じ色の要素がある」要素すべてからの距離がわかる必要はない。最短距離さえ分かっていれば良い。そのため，BFS を始めるときに「隣に同じ色の要素がある」要素をすべて queue に突っ込み，最短距離がわかった要素は二度訪れないようにすれば良い (多点 BFS や多始点 BFS などと言われている) 。

ソースコード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

using ll =  long long;
using Pii = pair<int, int>;

constexpr ll LINF = 1LL << 60;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int n, m; ll t;

bool check(int y, int x) {
    return (0 <= y) && (y < n) && (0 <= x) && (x < m);
}

int main() {
    cin >> n >> m >> t;
    vector<vector<ll>> a(n, vector<ll>(m));
    for(int i=0;i<n;++i) {
        string s;
        cin >> s;
        for(int j=0;j<m;++j) {
            a[i][j] = (s[j] - '0');
        }
    }

    vector<vector<ll>> dist(n, vector<ll>(m, LINF));
    queue<Pii> que;
    for(int i=0;i<n;++i) {
        for(int j=0;j<m;++j) {
            for(int k=0;k<4;++k) {
                int y = i + dyx[k][0], x = j + dyx[k][1];
                if(check(y, x) && a[i][j] == a[y][x]) {
                    dist[i][j] = 0;
                    que.emplace(i, j);
                    break;
                }
            }
        }
    }

    while(!que.empty()) {
        Pii p = que.front(); que.pop();
        for(int k=0;k<4;++k) {
            int y = p.first + dyx[k][0], x = p.second + dyx[k][1];
            if(check(y, x) && dist[y][x] == LINF) {
                dist[y][x] = dist[p.first][p.second] + 1;
                que.emplace(y, x);
            }
        }
    }

    int y, x; ll p;
    for(int i=0;i<t;++i) {
        cin >> y >> x >> p;
        --y; --x;
        cout << (a[y][x] + max(0LL, p-dist[y][x])) % 2 << "\n";
    }

}

所感

コンテスト中に解けなかった問題をコンテスト後に自力 AC すると悔しいことが知られている。

それはそれとして，問題自体は好きです。