ICPC2017 国内予選 D 弁当作り
問題
各成分が0, 1であらわされる行列Aが与えられる。
Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。
このようなA[i]のうち最大のサイズはいくつか。
例)Aが
010
011
110
101
だったら、2, 3, 4行目を選ぶと全ての列の和が偶数になり、このときの3つが最大。
制約条件
Aをn行m列としたときn, m≦500, nm≦500
解法
nm≦500という制約から、n, mのどちらかが小さい。
nが小さいときは行を2^n通り選んで実際に列の和が偶数になるかを見ればよい。
mが小さいときはdp[i][bit]をi行まで見たとき、各列の和(の2で割ったあまり)がbitになるときに選べる行の数の最大値とするようなテーブルとし、これを更新するbitDPをすればよい。
ソースコード
short dp[2][1 << 20]; template<int SZ> int solve(int n, int m){ if(SZ / 2 >= m) return solve<SZ / 2>(n, m); //bitsetのサイズを小さくしても大丈夫なら小さくする。(ただの高速化) int ans = 0; vector<bitset<SZ>> b(n); rep(i, n){ string s; cin >> s; rep(j, m) if(s[j] == '1') b[i][j] = 1; } rep(mask, 1 << n){ int k = __builtin_popcount(mask); if(ans >= k) continue; bitset<SZ> sum; rep(i, n) if(mask & 1 << i) sum ^= b[i]; if(sum.none()) ans = max(ans, k); } return ans; }; int main(){ cin.tie(0); cin.sync_with_stdio(0); int n, m; while(cin >> n >> m, n){ if(m > 20){ cout << solve<512>(n, m) << endl; } else{ memset(dp, -1, sizeof(dp)); vi b(n); rep(i, n){ string s; cin >> s; rep(j, m) if(s[j] == '1') b[i] |= 1 << j; } dp[0][0] = 0; int cur = 0, next = 1; rep(i, n){ memcpy(dp[next], dp[cur], sizeof(dp[cur])); rep(j, 1 << m) if(dp[cur][j] >= 0){ dp[next][j ^ b[i]] = max(dp[next][j ^ b[i]], (short)(dp[cur][j] + 1)); //dp[next][j] = max(dp[next][j], dp[cur][j]); } swap(cur, next); } cout << dp[cur][0] << endl; } } return 0; }