【AtCoder】ABC 460 D - Repeatedly Repainting

2026-06-08

AtCoder/ABC/D問題 AtCoder/ABC/425点問題 AtCoder/水Diff AtCoder/NoviSteps/1Q AtCoder/BFS/多始点BFS AtCoder/偶奇を考える競技プログラミング

D - Repeatedly Repainting

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1216 / NoviSteps: 1Q / 配点: 425 点

問題概要

$H \times W$ のグリッドがあり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼ぶ。

すべてのマスは白または黒で塗られていて、マス目の情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \ldots, S_H$ によって与えられ、 $S_i$ の $j$ 文字目が.のときマス $(i, j)$ は白で、 $S_i$ の $j$ 文字目が# のときマス $(i, j)$ は黒で塗られていることを表す。

これから、以下の操作を $10^{100}$ 回行う。

すべてのマスに対して同時に以下の規則で色の塗り替えを行う。
- 操作前に白く塗られているマスは、そのマスの8近傍に黒く塗られているマスが存在するときに限り黒く塗り替える。
- 操作前に黒く塗られているマスは、白く塗り替える。

操作を終えた後に各マスが何色で塗られているか求めよ。

制約

$1 \leq H \times W \leq 10^6$
$H, W$ は正整数
$S_i$ は ., # からなる長さ $W$ の文字列

考察

$10^{100}$ 回の操作のシミュレーションは不可能なので、各マスの色の変化に規則性がないかを考える。

1回目の操作では、初期状態で黒だったマスは必ず白になり、初期状態で白だったマスは、8近傍に黒マスが存在すれば黒になる。したがって、1回目の操作後に黒になるマスの集合 $B_1$ は、

B_1 = \left\{ (i, j) \mid (S_i[j] = \texttt{.}) \land (\text{8近傍に黒マスが存在}) \right\}

となる。これは、単純に各マスについて8近傍を調べることで $O(HW)$ の計算量で求めることができる。

ここで、 $B_1$ が空の場合、1回目の操作後に黒マスが存在しなくなる。以後、白マスを黒に変える原因となる黒マスが存在しないため、最終状態はすべて白になる。

一方、 $B_1$ が空でない場合は、1回目の操作以降、黒マスの影響が8近傍方向に1マスずつ伝わっていくと考えられる。したがって、各マスについて $B_1$ からの最短チェビシェフ距離を $d_m$ とすると、そのマスが初めて黒になる時刻は $1 + d_m$ である。

また、一度黒になったマスは次の操作で白になるが、周囲の黒マスの影響によって、その後は操作を行うごとに黒と白が交互に現れる。そのため、 $T = 10^{100}$ 回の操作を行った後のマスの色は、

\begin{cases} \text{黒} & (T - (1 + d_m) \text{ が偶数}) \\ \text{白} & (T - (1 + d_m) \text{ が奇数}) \end{cases} \iff \begin{cases} \text{黒} & (d_m \text{ が奇数}) \\ \text{白} & (d_m \text{ が偶数}) \end{cases}

となる。

最後に、すべてのマスについて $B_1$ からの最短チェビシェフ距離 $d_m$ を求める必要がある。

8近傍への移動コストはすべて $1$ なので、 $B_1$ に含まれる全マスを始点として多始点 BFS を行えばよい。計算量は、各マスを高々1回ずつ訪問し各マスから8方向を調べるため、 $O(HW)$ となる。

結局、全体の計算量は $O(HW)$ であり、これは本問の制約下で十分高速である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.using Pair_int = pair<int, int>;
6. 
7.// ======================================== //
8. 
9.int di[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
10.int dj[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
11. 
12.int main()
13.{
14.    int H, W;
15.    cin >> H >> W;
16.    vector<string> S(H);
17.    rep(i, 0, H) cin >> S[i];
18. 
19.    vector<Pair_int> B1;
20.    rep(i, 0, H) rep(j, 0, W) {
21.        if (S[i][j] == '.') {
22.            rep(dir, 0, 8) {
23.                int ni = i + di[dir], nj = j + dj[dir];
24.                if (0 <= ni && ni < H && 0 <= nj && nj < W && S[ni][nj] == '#') {
25.                    B1.emplace_back(i, j);
26.                    break;
27.                }
28.            }
29.        }
30.    }
31. 
32.    vector<vector<char>> ans(H, vector<char>(W));
33.    if (B1.empty()) {
34.        rep(i, 0, H) rep(j, 0, W) ans[i][j] = '.';
35.    }
36.    else {
37. 
38.        vector<vector<int>> dist(H, vector<int>(W, -1));
39.        queue<Pair_int> que;
40.        for (auto [i, j] : B1) {
41.            dist[i][j] = 0;
42.            que.emplace(i, j);
43.        }
44. 
45.        while (!que.empty()) {
46.            auto [i, j] = que.front();
47.            que.pop();
48. 
49.            rep(dir, 0, 8) {
50.                int ni = i + di[dir], nj = j + dj[dir];
51.                if (0 <= ni && ni < H && 0 <= nj && nj < W && dist[ni][nj] == -1) {
52.                    dist[ni][nj] = dist[i][j] + 1;
53.                    que.emplace(ni, nj);
54.                }
55.            }
56.        }
57. 
58. 
59.        rep(i, 0, H) rep(j, 0, W) {
60.            if (dist[i][j] % 2 == 0) {
61.                ans[i][j] = '.';
62.            }
63.            else {
64.                ans[i][j] = '#';
65.            }
66.        }
67.    }
68. 
69.    rep(i, 0, H) {
70.        rep(j, 0, W) cout << ans[i][j];
71.        cout << endl;
72.    }
73. 
74.    return 0;
75.}