WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM578 Div1 Easy "GooseInZooDivOne"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12539

カラスのキースは動物園のガチョウのケージを覗いている。
そのケージの床は正方形のマスで区切られている。
何羽かの鳥がそのマスで羽を休めている。(1マスにつき多くても1羽である)
彼らのうち何羽かがガチョウであり、その他はアヒルである。
キースはどの鳥がガチョウであるかを知りたい。
キースは次のような事を知っていた。

  • ケージには少なくとも1羽はガチョウがいる。
  • ガチョウは数は偶数である。
  • あるガチョウからマンハッタン距離でdist以内にいる鳥もまたガチョウである

あなたには文字列配列fieldとdistが与えられる。
fieldはケージの床の状態を表している。
各文字列の各文字は、1つのマスに対応している。
この文字は以下のような意味である。

  • 'v'という文字は、そのマスに鳥がいることを表している。
  • '.'という文字は、そのマスは何も無いことを表している。

ケージのガチョウの配置の仕方が何パターンあるかを返せ。
テストケースには、パターンが存在し得ないものがあることに注意せよ。

制約

1 <= マスの幅、高さ <= 50
1 <= dist <= 100


考えた事

Div2 Mediumとほぼ同じだが、ガチョウの数は偶数に制限されているなぁ
ってことは、グループの数を数えるときに、
偶数と奇数のそれぞれのグループ数を出して、
奇数グループは偶数個でしか使えないから(偶奇がややこしい・・)
答えは 2^(oddGloupNum / 2 + evenGloupNum) - 1 でいいんじゃね?

Sample通らん・・・

あ、例えば奇数グループが3つあった時は、
こっから0グループ使うのが3C0
こっから2グループ使うのが3C2
答えは3C0 + 3C2 - 1で3になるのか~
これまたmod_invとかやらなきゃ駄目なのかしら・・・

奇数グループ3つの場合だと

ここから0個使う・・・3C0 = 1パターン
ここから1個使う・・・3C1 = 3パターン <- 使えない
ここから2個使う・・・3C2 = 3パターン
ここから3個使う・・・3C3 = 1パターン <- 使えない

だから、1 + 3 = 4か・・・
これって3C0~3C3の総和をとって2で割ったのと同じだよね

奇数グループ4つの場合だと

ここから0個使う・・・4C0 = 1パターン
ここから1個使う・・・4C1 = 4パターン <- 使えない
ここから2個使う・・・4C2 = 6パターン
ここから3個使う・・・4C3 = 4パターン <- 使えない
ここから4個使う・・・4C4 = 1パターン

1 + 6 + 1 = 8
お、これも4C0~4C4の総和を2で割ったものじゃん!

3C0~3C3の総和・・・2^3
4C0~4C4の総和・・・2^4
5C0~5C5の総和・・・2^5
6C0~6C6の総和・・・2^6

おおお~、こんな性質があったのか!
ってことは奇数グループでは
2^(奇数のグループ数-1)でおっけーだ!


ソースコード

const int MOD = 1000000007;

class GooseInZooDivOne {
public:

    int H, W;
    vector<string> field;
    int dist;
    bool chk[55][55];    

    // マンハッタン距離
    int getDist( int ax, int ay, int bx, int by ){
        return abs( ax - bx ) + abs( ay - by );
    }

    // (x, y)から距離dist以内の鳥マスにチェックをつけ、マス数を返す
    int bfs_chk( int x, int y ){
        chk[y][x] = true;
        int cnt = 0;
        queue< pair<int,int> > que;
        que.push( make_pair( x, y ) );
        while( !que.empty() ){
            cnt++;
            int tx = que.front().first;
            int ty = que.front().second;
            que.pop();
            for( int ny = 0; ny < H; ny++ ){
                for( int nx = 0; nx < W; nx++ ){
                    if( field[ny][nx] != 'v' || chk[ny][nx] ) continue;
                    if( dist < getDist( tx, ty, nx, ny ) ) continue;
                    chk[ny][nx] = true;
                    que.push( make_pair( nx, ny ) );
                }
            }
        }
        return cnt;
    }

    int count(vector <string> _field, int _dist){
        field = _field;
        H = field.size();
        W = field[0].length();
        dist = _dist;
        memset(chk, false, sizeof(chk) );

        

        // 偶数のグループ、奇数のグループを数える
        int odd = 0, even = 0;
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( field[y][x] != 'v' || chk[y][x] ) continue;
                int cnt = bfs_chk( x, y );
                if( cnt % 2 ){
                    odd++;
                }else{
                    even++;
                }
            }
        }

        // グループで計算
        long long res = 1;
        if( odd > 0 ){
            // 奇数グループ
            for( int i = 0; i < odd - 1; i++ ){
            res = res * 2 % MOD;
            }
        }
        // 偶数グループ
        for( int i = 0; i < even; i++ ){
            res = res * 2 % MOD;
        }
                
        return (int)( res - 1 );
    }
};