AOJ 2299 Tiles are Colorful

問題概要
N×Mのグリッドが与えられる。各空白マスについて上下左右を見た時、最も近いアルファベット付きマスを取り出し、同じ文字のペアが存在する場合削除する。
これを繰り返したとき最大いくつ削除できるか。

考えたこと
各文字はせいぜい0か2個しか含まれないため、そろったものから貪欲に消していけばよいことが分かる

計算時間は各マスを調べるためにO(NM)、そこから上下左右のマスを調べるためにO(logN + logM)、これを何回か繰り返すのでだいたいO(NM*(logN+logM))

（二分探索をつかわずとも愚直に上下左右を調べるのでも間に合うっぽい）

ACコード

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

#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

bool erased[510][510];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    
    
    int H, W; cin >> H >> W;
    vector<string> f;
    REP(i,H){
        string s; cin >> s;
        f.push_back(s);
    }

    

    int ans = 0;
    bool update = true;
    while(update){
        update = false;
        vector<pair<int, char>> h[510], w[510];
        REP(i,H){
            h[i].push_back({-1, '0'});
            REP(j,W){
                if(f[i][j] != '.'){
                    //横方向に文字を見ていく
                    h[i].push_back({j, f[i][j]});
                }
            }

            h[i].push_back({INT_MAX, '0'});
        }

        REP(j,W){
            w[j].push_back({-1, '0'});
            REP(i,H){
                if(f[i][j] != '.'){
                    //縦方向に文字を見ていく
                    w[j].push_back({i, f[i][j]});
                }
            }

            w[j].push_back({INT_MAX, '0'});
        }

        memset(erased, false, sizeof(erased));

        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(f[i][j] == '.'){
                    //左右上下の文字を取得

                    //横方向
                    auto itr1 = lower_bound(all(h[i]), make_pair(j, '0'));
                    
                    //縦方向
                    auto itr2 = lower_bound(all(w[j]), make_pair(i, '0'));

                    pair<int, char> up,left,right,down;
                    right = *(itr1);
                    down = *(itr2);

                    itr1--;
                    itr2--;
                    
                    left = *(itr1);
                    up = *(itr2);
                    
                    
                    if(up.second != '0'){
                        if(up.second == left.second){
                            erased[up.first][j]=true;
                            erased[i][left.first]=true;
                        }
                        if(up.second == right.second){
                            erased[up.first][j]=true;
                            erased[i][right.first]=true;
                        }
                        if(up.second == down.second){
                            erased[up.first][j]=true;
                            erased[down.first][j]=true;
                        }
                    }
                    if(left.second != '0'){
                        if(left.second == right.second){
                            erased[i][left.first]=true;
                            erased[i][right.first]=true;
                        }
                        if(left.second == down.second){
                            erased[down.first][j]=true;
                            erased[i][left.first]=true;
                        }
                    }
                    if(right.second != '0'){
                        if(right.second == down.second){
                            erased[down.first][j]=true;
                            erased[i][right.first]=true;
                        }
                    }
                }
            }
        }

        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(erased[i][j]){
                    ans++;
                    f[i][j] = '.';
                    update = true;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}