AOJ 1619 - 弁当作り - ツバサの備忘録

制約に $n \times m \leqq 500$ と書いてあります。これがすべてです。
$n$ が大きいパターンと $m$ が大きいパターンで場合分けをします。
$\sqrt{500} \lt 23$ なので、実は $min(n,m)$ が、簡単にビットで情報を持つことができます。

$n$ が小さいパターン
全探索をします。
それぞれの材料について、その材料を必要としているレシピの集合を前計算で求めておきます。
そして、今回作成するレシピの集合 $s$ について、先ほどの前計算したものとそれぞれ積集合を計算し、その結果含まれる要素の個数が全て偶数であれば、 $s$ のレシピの集合を一度に作成することができます。この $s$ のうち、要素数が最大のものを求めればよいです。
$m$ が小さいパターン
bitDPをします。
$dp[i][s] = i$ 番目までのレシピを作成し終えて、材料の余りが $s$ になるようなレシピの作成方法のうち、作成したレシピの個数の最大値
とすると、 $i$ 番目のレシピを作成した際に使用する材料の集合を $p_{i}$ として前計算しておくことで、
$dp[i + 1][s] = max(dp[i][s], dp[i][s \bigtriangleup p_{i}] + 1)$
という遷移で計算することができます。
$s \bigtriangleup p_{i}$ は $s$ と $p_{i}$ のxorをとればよいです。
こうすると、 $dp[n][0]$ が答えになります。

あとは、この計算を繰り返せば答えが求まります。

感想

制約によって場合分けをする発想が無かったので解けませんでした…(それぞれについては、この制約ならいけるのになぁみたいな感じでなんとなくは考えていました)。