ABC018 - C - 菱型カウント

ABC - C埋めを再開しました。解説ACです。

問題

atcoder.jp

考えたこと

ひし形の中心でループ回して探索してく。

行/列のループを回せば、r <= 50, c<= 50の制約はクリアできるので部分点はもらえるけれど…。ひし形の判定の計算量を落とす方法がわからなかった。

解答

ここを参考にした。 qiita.com

要は累積和っぽいことをするとよくて、左から右へ向かって、そのマスが白マス何個連続しているかを前処理で持っておくようにした。

リンク先によると、こういうデータ列が与えられたときにとりあえず累積和を取る、というのはセオリー的な技みたい。

ソースを開く

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

int main(){

    long r,c,k;
    cin >> r >> c >> k;

    vector<string> m(r);
    rep(i,r) cin >> m[i];

    vector<vector<long>> ru(r, vector<long>(c + 1, 0));

    // 'o'の連続個数の和？
    rep(i,r){
        rep(j,c){
            if(m[i][j] == 'o'){
                ru[i][j + 1] = ru[i][j] + 1;
            }
        }
    }

    long ans = 0;

    long s_r,s_c,e_r,e_c;
    s_r = k - 1;
    s_c = k - 1;

    e_r = r - k;
    e_c = c - k;

    // ひし形の中心で探索する
    for(int x = s_c; x <= e_c; x++){
        for(int y = s_r; y <= e_r; y++){

            // ひし形のてっぺんを計算する
            long t_x = x;
            long t_y = y - k + 1;

            // ひし形のてっぺんからしたまで右端を見ていく
            long i = 0; // 下方向
            long j = 0; // 右方向
            long wid = 1;
            bool flg = true;

            for(; i < 2 * k - 1; i++){
                long c_x = t_x + j;
                long c_y = t_y + i;

                if(ru[c_y][c_x + 1] < wid * 2 - 1){
                    flg = false;
                    break;
                }

                if(i < k - 1){
                    j++;
                    wid++;
                } else {
                    j--;
                    wid--;
                }
            }

            if(flg) ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

学んだこと

• データ列が与えられたときはとりあえず累積和ととってみる。
• 計算量を減らす手段として、次元を減らしましょう。（たとえば今回のだと、累積和をとって横方向の判定をO(1)にしたり。）

感想

gridは頭こんがらがる。