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だし方向性はあってたんだけどダブルカウントとか訳わからなくなってきて自力で解けませんでした。頭の回転…………