JOI 本選 2014 A - JOI紋章 (AOJ 0598, 難易度 6)

ちょっと実装大変だった。差分のみ更新していく系の問題。

• 問題へのリンク
• editorial

問題概要

のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。

またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。

今、与えられたグリッドのうちの 1 マスの文字を自由に書き換えることができる。書き換えてできたグリッドにおいて「パターンが一致する箇所」が何箇所あるか、考えられる最大値を求めよ。

制約

• 

考えたこと

まずそもそも、文字を書き換える前のグリッドのスコアを求めておく。この作業は でできる。具体的には、各「2 × 2」について

• 与えられたパターンに一致するならば：スコア 1
• 与えられたパターンに一致しないならば：スコア 0

として、これらを合算していけば OK。

マスの文字の書き換え

次に、各マス ( 通り) を各文字 (3 通り) に書き換えることによる影響を順に調べていきたい。このとき 通りそれぞれについてスコアを最初から求めなおしたのでは の計算量となってしまって間に合わない。

ここで、次の点に着目する。

• マス を書き換えたとき
• それによって影響が発生しうる「2 × 2」は、その周囲の 4 箇所のみである (下図参照、赤く塗り潰したマスを書き換えたときの影響は 4 箇所のみ)

それ以外の「2 × 2」については、スコアは変動しない。よって、

• 書き換える前の、4 箇所の「2 × 2」のスコアの合計値
• 書き換えた後の、4 箇所の「2 × 2」のスコアの合計値

として、 の最大値を求めればよい。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> fi(H), pat(2);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    for (int i = 0; i < 2; ++i) cin >> pat[i];

    auto calc = [&](int i, int j) -> int {
        if (i < 0 || i+1 >= H || j < 0 || j+1 >= W) return 0;
        for (int di = 0; di <= 1; ++di) {
            for (int dj = 0; dj <= 1; ++dj) {
                if (fi[i+di][j+dj] != pat[di][dj]) return 0;
            }
        }
        return 1;
    };
    auto calc2 = [&](int i, int j) -> int {
        return calc(i-1, j-1) + calc(i-1, j) + calc(i, j-1) + calc(i, j);
    };

    int res = 0;
    for (int i = 0; i < H; ++i) 
        for (int j = 0; j < W; ++j)
            res += calc(i, j);
    int add = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            char origin = fi[i][j];
            int before = calc2(i, j);

            string joi = "JOI";
            for (auto c: joi) {
                fi[i][j] = c;
                int after = calc2(i, j);
                chmax(add, after - before);
            }
            fi[i][j] = origin;
        }
    }
    cout << res + add << endl;
}