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 ); } };