Hatena::Grouptopcoder

peryaudoのTopCoder日記

2016-04-19

Subsets

| 13:56

#include <vector>
#include <map>
#include <iostream>

using namespace std;
using ll = long long;

class Subsets {
 public:
  int findSubset(vector<int> numbers) {
    int ones = 0;
    map<int, int> cnts;
    for (int num : numbers) {
      if (num == 1) {
        ++ones;
      } else {
        ++cnts[num];
      }
    }

    for (auto&& cnt : cnts) {
      nums.push_back(cnt);
    }

    return F(0, 0, 1, ones) + max(0, ones - 1);
  }

  int F(int idx, int sum, int prod, int ones) {
    if (idx >= nums.size()) return 0;

    int ans = 0;
    if (ones - (prod * 2 - sum - 2) > 0)
      ans += F(idx + 1, sum, prod, ones);
    for (int i = 1; i <= nums[idx].second; ++i) {
      const ll nsum = (ll)sum + (ll)nums[idx].first * i;
      const ll nprod = (ll)prod * ipow(nums[idx].first, i);
      if (ones > nprod - nsum) {
        ans += ones - (nprod - nsum);
        ans += F(idx + 1, nsum, nprod, ones);
      }
    }
    return ans;
  }

  int ipow(int m, int e) {
    int ans = 1;
    for (int i = 0; i < e; ++i) {
      if (ans >= ans * m) return 100000;
      ans *= m;
    }
    return ans;
  }

  vector<pair<int, int>> nums;
};

やっと久々にACした………ただのオーバーフローと枝刈り不足で苦しんでました。