【AtCoder】ABC 337 D - Cheating Gomoku Narabe | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 760

問題概要

各マスにo, x, .のいずれかの文字が書かれた $H$ 行 $W$ 列のグリッドがある。以下、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ とする。このグリッドに対して、下記の操作を $0$ 回以上好きな回数だけ繰り返す。

.が書かれているマスを1つ選び、そのマスに書かれた文字をoに置き換える。

その結果、縦方向または横方向に連続した $K$ 個のマスであって、それらに書かれた文字がすべてoであるようなものが存在するようにすることが可能かを判定し、可能な場合はそのために行う操作回数の最小値を出力せよ。不可能な場合は-1を出力せよ。

制約

$H, W, K$ は整数。
$1 \leq H, W, \quad H \times W \leq 2 \times 10^5$
$1 \leq K \leq \max(H, W)$

考察

問題文に書かれている満たされるべき条件の記述と $H \times W \leq 2 \times 10^5$ という制約から、各行と列を順に探索していくことを考えるのが自然だろう。以下では、ある行に対して「横方向に連続した $K$ 個のマスであって、それらに書かれた文字がすべてoであるようなものが存在するようにすることが可能か」どうかを判定することを考える。

この条件を満たすのは、閉区間 $[i, i + K - 1] \: (1 \leq i \leq W - K + 1)$ の中に含まれる $K$ 個のマスの中にxが1つも存在しないときである。さらに、このときの操作の最小回数は $K$ 個のマスの中の.の個数に他ならない。

ここまではおそらく考察しやすいのだが、問題は $K$ 個のマスの中に含まれるxと.の個数の数え方だ。既に計算量 $O(HW)$ のループを回しているため、なんとかして $O(1)$ 程度で計算しなければならない。

ある区間の個数(総和)を求めるクエリを爆速で処理するテクニック...

ここで思いつきたいのが累積和だ。あらかじめ閉区間 $[1, i] \: (i = 1, 2, \cdots, W)$ の中に含まれるマスの中のxと.の個数を記録しておき、あとは累積和を取ることによって $O(1)$ で各区間のそれぞれの個数を求めることができる。

同じことを列に対しても行い、その中で最小の.の個数を記録しておく。最終的にその個数が $K$ 個以下なら条件を満たし、そうでなければ満たさない。

累積和を用いるときにはインデックスの参照エラーが起きやすいので注意しよう。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> rows(H);
    rep(i, 0, H) cin >> rows[i];
    vector<string> cols(W);
    rep(i, 0, W) rep(j, 0, H) cols[i] += rows[j][i];

    int ans = INF;
    vector<int> X(200020, 0), E(200020, 0);
    rep(i, 0, H)
    {
        X[0] = 0;
        E[0] = 0;
        rep(x, 0, W)
        {
            X[x + 1] = X[x];
            E[x + 1] = E[x];

            if (rows[i][x] == 'x')
                X[x + 1]++;
            if (rows[i][x] == '.')
                E[x + 1]++;
        }

        rep(x, 0, W - K + 1)
        {
            if (X[x + K] - X[x] == 0)
                chmin(ans, E[x + K] - E[x]);
        }
    }

    rep(i, 0, W)
    {
        X[0] = 0;
        E[0] = 0;
        rep(y, 0, H)
        {
            X[y + 1] = X[y];
            E[y + 1] = E[y];

            if (cols[i][y] == 'x')
                X[y + 1]++;
            if (cols[i][y] == '.')
                E[y + 1]++;
        }

        rep(y, 0, H - K + 1)
        {
            if (X[y + K] - X[y] == 0)
                chmin(ans, E[y + K] - E[y]);
        }
    }

    if (ans > K)
        ans = -1;

    cout << ans << endl;
}