Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2016-04-19

PowersOfTwo

| 15:31

#include <map>
#include <vector>
using namespace std;


class PowersOfTwo {
 public:
  long long count(vector<long long> powers) {
    nums = vector<int>(65);
    for (long long p : powers) {
      int dig = 0;
      while ((1LL << dig) <= p) ++dig;
      ++nums[dig];
    }

    return F(0, 0);
  }

  long long F(int dig, int carry) {
    if (dig >= 60) return 1;
    if (carry < 0) return 0;
    if (memo.count(make_pair(dig, carry))) return memo[make_pair(dig, carry)];

    const int ncarry = carry + nums[dig];
    if (ncarry == 0)  {
      memo[make_pair(dig, carry)] = F(dig + 1, 0);
    } else {
      memo[make_pair(dig, carry)] = F(dig + 1, ncarry / 2) + F(dig + 1, (ncarry - 1) / 2);
    }
    return memo[make_pair(dig, carry)];
  }

  map<pair<int, int>, long long> memo;
  vector<int> nums;
};

簡単なDPだし方向性はあってたんだけどダブルカウントとか訳わからなくなってきて自力で解けませんでした。頭の回転…………

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した………ただのオーバーフローと枝刈り不足で苦しんでました。

 |