ICPC 2017 国内予選: D. 弁当作り

この記事は解説 Advent Calendar 2017 - Adventar15日目の記事です。

問題

http://icpc.iisf.or.jp/past-icpc/domestic2017/contest/all_ja.html#section_D

解法

の大小で場合分け。オーダーはより軽くなる。

が小さい時、それぞれのレシピについて使う使わないをすべて試す全探索。
材料を偶数個ずつ使う条件を満たす中でレシピ数が最も多いものを返す。

が小さい時、ナップサック問題のような易しいdp問題である。
それぞれの材料について使った回数の偶奇のみを保持すればよい。
具体的にはレシピごとのという入力を2進数として扱えるよう変換する。これをとする。
レシピの選び方が条件を満たすということは選んだレシピについて
の排他的論理和をとると0になるということである。

とし、
で更新できる。
はじめ、であり、が答え。

自分の実装では配列を使いまわしてメモリを節約するテクをしているので注意。

一言

であることの意味と、の大小で場合分けであることに、
気づけるかどうかがポイント。
悲しいことに本番でという変換をしてしまい、詰んだ。
あと国内予選って実装力も求められるよね。

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define pb push_back

int N, M;
string B[514];
bool E[514];
int dp[1 << 24][2];

//N < M
void mode1() {
  int ans = 0;
  rep(i, 1 << N) {
    rep(j, M)E[j] = false;
    int cnt = 0;
    rep(j, N) {
      if (i >> j & 1) { //use No.j
        cnt++;
        rep(k, M) {
          if (B[j][k] == '1')E[k] = !E[k];
        }
      }
    }
    bool flag = true;
    rep(j, M)if (E[j])flag = false;
    if (flag) ans = max(ans, cnt);
  }
  cout << ans << endl;
}

//N >= M
void mode2() {
  rep(i, 1 << M)dp[i][0] = -1;
  dp[0][0] = 0;
  bool k = 1;
  rep(i, N) {
    int W = 0;
    int d = 1;
    rep(j, M) { //入力を2進数に変換
      W += d * (B[i][M - j - 1] == '1');
      d *= 2;
    }
    rep(j, 1 << M)dp[j][k] = dp[j][!k];
    rep(j, 1 << M) {
      if (dp[j][!k] >= 0) {
        int x = j^W;
        dp[x][k] = max(dp[j][!k] + 1, dp[x][k]);
      }
    }
    k = !k;
  }
  cout << dp[0][!k] << endl;
}

int main() {
  while (true) {
    cin >> N >> M;
    if (N == 0 && M == 0)return 0;
    rep(i, N) cin >> B[i];
    if (N < M)
      mode1();
    else
      mode2();
  }
}