概要
グリッド状のケージの中に何羽かの鳥がいる。
グリッドは文字列の配列で表され、文字が 'v' のところには一羽の鳥がおり、'.' のところにはいない。
鳥はガチョウとアヒルの二種類がいて、次の条件を満たす
- ケージの中には一羽以上のガチョウがいる
- ガチョウの数は偶数である
- いずれかのガチョウとマンハッタン距離が dist 以下の全ての鳥はガチョウである
鳥の配置として可能なものの総数を求めよ。
解法
マンハッタン距離が dist 以下の鳥のペアをグループ化していくことを考えます。
このとき、一羽の鳥はちょうど一つのグループに属します。
ある鳥をガチョウと決めると、同じグループに属する鳥は全てガチョウになります。
前処理として、鳥のグループを( DFS|BFS|UnionFind木)で求め、このグループ数を N とします。
また各グループについて、属する鳥の数も求めておき、
groups[i] := i 番のグループに属する鳥の数
としておきます。
dp[ 考慮したグループ数 ][ ガチョウの数 ] := 場合の数
として DP をします。
状態遷移は以下の二つです。
- 現在のグループをアヒルにする -> dp[ i ][ j ] から dp[ i + 1 ][ j ] を更新
- 現在のグループをガチョウにする -> dp[ i ][ j ] から dp[ i + 1 ][ j + groups[ i ] ] を更新
最後に、dp[ N ][ { x | x = { 2, 4, 8 ... } } ] の総和をとったものが答えになります。
コード
typedef long long LL; typedef vector<int> VI; typedef vector<string> VS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) const int MOD = 1000000007; typedef vector<LL> VL; typedef vector<VL> VVL; class GooseInZooDivOne { public: int H, W, dist; VS board; int count( vector <string> field, int dist ) { this -> board = field; this -> dist = dist; this -> H = field.size(); this -> W = field[0].size(); int numv = 0; REP( i, 0, H ) { numv += std::count( ALL( board[i] ), 'v' ); } VI groups; REP( i, 0, H ) { REP( j, 0, W ) { if ( board[i][j] == '.' ) { continue; } groups.PB( dfs( i, j ) ); } } const int N = groups.size(); VVL dp( N + 1, VL( H * W + 1, 0 ) ); dp[0][0] = 1; REP( i, 0, N ) { REP( j, 0, dp[i].size() ) { dp[i][j] %= MOD; dp[ i + 1 ][j] += dp[i][j]; if ( j + groups[i] <= dp[i].size() ) { dp[ i + 1 ][ j + groups[i] ] += dp[i][j]; } } } LL res = 0; for ( int i = 2; i < dp[N].size(); i += 2 ) { res += dp[N][i]; res %= MOD; } return res; } int dfs( int y, int x ) { if ( !inside( y, x ) || board[y][x] == '.' ) { return 0; } board[y][x] = '.'; int res = 1; REP( i, 0, H ) { REP( j, 0, W ) { if ( abs( i - y ) + abs( j - x ) <= dist ) { res += dfs( i, j ); } } } return res; } bool inside( int y, int x ) { return 0 <= y && y < H && 0 <= x && x < W; } };