ACM-ICPC 2017 国内予選: D. 弁当作り
問題文の$1 \le n \times m \le 500$は太字で書かれていて親切。しかし印刷した紙ではまったく気付かなかった。
solution
$n \times m \le 500$の制約を使って場合分け。$n$が小さいときはレシピの部分集合を全部試して$O(2^nm)$。$m$が小さいときは余った食材を引数とするDPで$O(n2^m)$。
implementation
#include <bitset>
#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++ (i))
using namespace std;
int main() {
while (true) {
int n, m; cin >> n >> m;
if (n == 0 and m == 0) break;
vector<vector<bool> > b(n, vector<bool>(m));
repeat (y, n) {
repeat (x, m) {
char c; cin >> c;
b[y][x] = c - '0';
}
}
int result = 0;
// if ((1ll << n) < (n * (1ll << m))) {
if (m >= 20) {
// n is small
vector<bitset<500> > bs(n);
repeat (y, n) {
repeat (x, m) {
bs[y][x] = b[y][x];
}
}
vector<pair<bitset<500>, int> > cur, prv;
cur.emplace_back(bitset<500>(), 0);
repeat (i, n) {
cur.swap(prv);
cur = prv;
for (auto const & it : prv) {
bitset<500> bs_j; int cnt; tie(bs_j, cnt) = it;
if ((bs[i] ^ bs_j).none()) {
result = max(result, cnt + 1);
}
cur.emplace_back(bs[i] ^ bs_j, cnt + 1);
}
}
} else {
assert (m < 30);
// m is small
vector<int> bi(n);
repeat (y, n) {
repeat (x, m) {
if (b[y][x]) {
bi[y] |= 1 << x;
}
}
}
vector<int> cur(1 << m, -1), prv;
cur[0] = 0;
repeat (i, n) {
cur.swap(prv);
cur = prv;
repeat (j, 1 << m) if (prv[j] != -1) {
if ((bi[i] ^ j) == 0) {
result = max(result, prv[j] + 1);
}
cur[bi[i] ^ j] = max(cur[bi[i] ^ j], prv[j] + 1);
}
}
}
cout << result << endl;
}
}