Regionals 2010 :: Europe - Southeastern

Dだけ

Live Archive 4819 - Problemsetting

問題

N個のコンテストがあり、M個の問題がある。
それぞれのコンテストは、必要な問題数が決まっており、それぞれの問題は、出題できるコンテストが決まっている。
このとき、与えられた問題を使って開催できるコンテストの最大数を求めよ。

制約

1 < N < 15, 0 < M < 50
必要な問題数<=100

解法

マッチングっぽいので、最大流を使いたい。
実際、全てのコンテストの組み合わせについてグラフを構成し、最大流を流すという方法で解ける。
このとき、全ての場合で最大流をするとTLEするので、明らかに必要な流量が流れない場合や、今までに求められた答えより改善されないような組み合わせは無視する。
これでもいいが、ホールの定理で解けるということを知ったので、ホールの定理を使って解いてみた（本題）。

ホールの定理について、詳しくはホールの定理 - Wikipedia

いま、あるコンテストについて、そのコンテストに使える問題の集合をとする。
このとき、そのコンテストに必要な問題の数の分だけその集合を複製する。
これらをまとめた（多重）集合をとするとき、の部分集合の横断集合（SDR）が存在すれば、に対応するコンテストの組み合わせを開催することが出来る。
ホールの定理より、の横断集合が存在することの必要十分条件は、の全ての部分集合について、

が成り立つことである。この結婚条件を示すことが出来れば、そのコンテストの組み合わせを開催することが出来ると言える。

サンプル１を考えると、は、

• IOI = {1,3,4} が３個
• TopCoder = {2,5} が２個
• IPSC = {2,3,4} が２個
• SEERC = {5} が10個

となる。
ここで、として、{IOI,TopCoder}を考えると、{1,2,3,4,5}という横断集合が存在するので、{IOI,TopCoder}を開催することが出来る。

結婚条件を満たすかどうか調べるとき、としては、複製された集合の一部を取ってくるのは意味無いので、を含むか含まないかのパターンを見てやれば良い。
全部を素朴に計算すると計算量がやばそうなので、DPした。（もしかして素朴にやっても3^Nとかで間に合う？）
が結婚条件を満たさないようながあるとき、も結婚条件を満たさない。
そうでないときは、が結婚条件の不等式を満たすかどうかを見てやれば良い。
このような発想でDPをすることができる。
不等式の両辺の値は前計算で求めておくことが出来る。

ソース

ll f[15];                       // f[i] = set of problems for contest i 
int sum[1<<15];                     // sum[S] = sum of num[i] for i in S
ll uni[1<<15];                     // uni[S] = union of f[i] for i in S
bool dp[1<<15];

int num[15];

int main() {
  int cs = 0;
  int n, m;
  
  while(cin>>n>>m,n||m) {
    map<string,int> mp;
    REP(i,n) {
      string s;
      cin >> s >> num[i];
      mp[s] = i;
    }
    string line;
    getline(cin,line);
    memset(f,0,sizeof(f));
    REP(i,m) {
      getline(cin,line);
      stringstream ss(line);
      string s;
      while(ss>>s) {
        f[mp[s]] |= 1LL<<i;
      }
    }
    memset(sum,0,sizeof(sum));
    memset(uni,0,sizeof(uni));
    REP(i,n) {
      REP(S,1<<i) {
        sum[S|1<<i] = sum[S]+num[i];
        uni[S|1<<i] = uni[S] | f[i];
      }
    }
    int ans = 0;
    REP(S,1<<n) {
      dp[S] = 1;
      REP(i,n) {
        if (S>>i&1) {
          if (!dp[S^(1<<i)]) dp[S] = 0;
        }
      }
      if (sum[S] > __builtin_popcountll(uni[S])) dp[S] = 0;
      if (dp[S]) {
        ans = max(ans, __builtin_popcount(S));
      }
    }
    printf("Case #%d: %d\n", ++cs, ans);
  }
}