【ABC410 F問題】考察から実装(c++)まで

Last updated at 2025-06-17Posted at 2025-06-17

AtCoderBeginnerContest410の解説＆感想です。
コンテストリンク

問題一覧

F問題 - Balanced Rectangles

問題リンク

問題概要

$H \times W$の二次元グリッドが与えられる。グリッドの各マスには.か#のどちらかが書かれている。以下を満たす長方形領域をすべて数え上げよ。

領域に含まれる.の個数と#の個数が等しい

$T$個のテストケースが与えられるので、それぞれ解いて答えを一行で表示せよ。

制約

$1 \le T \le 25000$
$1 \le H,W$
$H \times W $の総和は$3 \times 10^5$を超えない

考察

全ての長方形を数えようとすると$O((HW)^2)$かかってしまうので、なんとかしたい。
どうしよっかなーと思って問題を眺めると、

.を$1$、#を$-1$に対応させる

という対応をまず思いつく。こうしておくと、解くべき問題を

内部の総和が0の長方形領域を全て数え上げる

と言い換えることができる。
結局まだ計算量は改善されていないので、どげんかする必要はある。

こういう時はどこかを固定して考えるといいと偉い人が言っていたので、縦幅(上の行を$u$、下の行を$d$とする)を一つ固定すると、横方向に一次元の問題にできることに気がつく。
各列に対して累積和をとっておくと、それぞれの列での$u$から$d$までの合計はすぐにわかるので、$j$列目の$u$から$d$までの合計を$R(u,d)_j$とか表すと、

一次元配列$R(u,d)_1, R(u,d)_2,...,R(u,d)_W$に対して、合計が$0$になる区間を全て数える

という問題になる。
これを$O(W)$で解ければよさそう。

これはもう少し言い換えると、配列$R(u,d)$の累積和をとった配列$C_1,C_2,,,,C_W$に対して、

$C_j-C_i=0 \Leftrightarrow C_j = C_i$となる数字の組$i,j(i < j)$を全て数える

となる。
これは今まで出た$C_i$のカウントをmapなどで数えていけばいいが、mapだと計算量がギリギリなので、unordered_mapを使うことにする。

これで計算量$O(H^2W)$で解けるけど、$H=3\times10^5,W=1$とかの時に余裕でTLEになってしまうので、$H > W$の時は90度回転するなり転置するなりしておく必要がある。
そうすれば、$min(H,W) \le \sqrt{3\times 10^5} \fallingdotseq 548$なので、最大でも$1.6\times10^8$とかにできて、キリッキリ間に合いそう。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vs = vector<string>;


template<typename T>
vector<vector<T>> transpose(vector<vector<T>> &a){
    ll h = a.size();
    ll w = a[0].size();
    
    vector<vector<T>> ret(w, vector<T>(h));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ret[j][i] = a[i][j];
        }
    }
    return ret;
}


int solve(){
    //入力
    ll H,W;
    cin>>H>>W;
    
    vs S(H);
    for(int i=0;i<H;i++) cin>>S[i];
    
    //.を1、#を-1に対応させた配列を作る
    vvll g(H, vll(W));
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            g[i][j] = (S[i][j]=='.'?1:-1);
        }
    }
    
    //Hがでかすぎたら転置
    if(H > W){
        g = transpose(g);
        swap(H,W);
    }
    
    //各列の累積和をとる
    vvll r(H+1, vll(W,0));
    for(int j=0;j<W;j++){
        for(int i=0;i<H;i++){
            r[i+1][j] = r[i][j]+g[i][j];
        }
    }
    
    ll ans = 0;
    unordered_map<ll,ll> cnt;
    //縦幅を固定する
    for(int u=0;u<H;u++){
        for(int d=u;d<H;d++){
            //ここでC_i == C_jとなる組み合わせの個数を数える
            cnt.clear();
            ll c = 0;
            cnt[c]++;
            for(int j=0;j<W;j++){
                c += r[d+1][j]-r[u][j];
                ans += cnt[c];
                cnt[c]++;
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

int main(void){
    ll T;
    cin>>T;
    
    while(T--) solve();
}

その他問題

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up