Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2016-04-21

VocaloidsAndSongs

| 10:57

#include <iostream>
#include <map>
#include <tuple>

using namespace std;

class VocaloidsAndSongs {
 public:
  int count(int S, int gumi, int ia, int mayu) {
    return F(S, gumi, ia, mayu);
  }

  int F(int rem, int gumi, int ia, int mayu) {
    if (memo.count(make_tuple(rem, gumi, ia, mayu)))
      return memo[make_tuple(rem, gumi, ia, mayu)];
    int& ans = memo[make_tuple(rem, gumi, ia, mayu)];
    if (rem == 0) {
      return ans = (gumi == 0 && ia == 0 && mayu == 0 ? 1 : 0);
    }

    for (int i = 1; i < (1 << 3); ++i) {
      int ngumi = gumi - ((i & 1) ? 1 : 0);
      int nia = ia - ((i & 2) ? 1 : 0);
      int nmayu = mayu - ((i & 4) ? 1 : 0);
      if (ngumi < 0 || nia < 0 || nmayu < 0) continue;
      ans += F(rem - 1, ngumi, nia, nmayu);
      ans %= 1000000007;
    }
    return ans;
  }

  map<tuple<int, int, int, int>, int> memo;
};

結構難易度にばらつきありまんね…

 |