SRM578 Div1 Easy - GooseInZooDivOne
問題
h*wのグリッド上のいくつかのマスにガチョウとアヒルがいるが、見た目で区別はつかない
ガチョウは以下の条件を満たす
1) ガチョウは2以上の偶数匹いる
2) あるガチョウからマンハッタン距離がd以内にいるような鳥は必ずガチョウである
鳥の部分集合のうち、全要素がガチョウであり得るようなものの個数を求めよ
1 <= h, w <= 50
0 <= d <= 100
解法
各鳥を頂点0〜n-1とし、マンハッタン距離がd以下であるような鳥のペア間に辺を引いてグラフを作る
条件2より各連結成分の鳥は全てガチョウかアヒルのどちらかで統一される必要がある
i番目の連結成分のサイズをa[i]として(0 <= i < m)、
dp[i][j]: a[0]〜a[i-1]の範囲でガチョウがj匹になるような選び方の個数
を埋めればok
答えはΣdp[m][even]
実装
辺の情報を全部記録しちゃうとスタックオーバーフローするケースがありそう
(50*50で全マスにガチョウがいるときなんかが怪しい)
記録はせずに再帰で毎回チェックする
dp配列も同様にメモリ節約しないとダメ
class GooseInZooDivOne { public: int h, w, n, m, d, dp[2][2525], res; bool f[2525]; vector<int> x, y, a; int rec(int v) { f[v] = 1; int res = 1; rep(i,n) if (!f[i] && abs(x[v]-x[i])+abs(y[v]-y[i])<=d) res += rec(i); return res; } int count(vector<string> s, int d_) { d = d_, h = s.size(), w = s[0].size(); rep(i,h) rep(j,w) if (s[i][j]=='v') x.push_back(i), y.push_back(j), n++; rep(i,n) if (!f[i]) a.push_back(rec(i)), m++; dp[0][0] = 1; rep(I,m) { int i = I&1; rep(j,n) if (dp[i][j]) { (dp[i^1][j+a[I]] += dp[i][j]) %= mod; (dp[i^1][j] += dp[i][j]) %= mod; } memset(dp[i], 0, sizeof(dp[i])); } int res = 0; reps(i,2,n+1) if (i%2==0) (res += dp[m&1][i]) %= mod; return res; } };
d以下じゃなくてちょうどdと誤読した
https://community.topcoder.com/stat?c=problem_statement&pm=12539&rd=15498