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;
};

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

2014-03-03

MagicalStringDiv1

| 14:57

#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#include <numeric>

using namespace std;


class MagicalStringDiv1 {
public:
	int getLongest(string S) {
		int res = 0;
		for (int i = 0; i <= S.size(); ++i) {
			const string lhs = S.substr(0, i);
			const string rhs = S.substr(i);
			res = max<int>(res,
					2 * min(count(lhs.begin(), lhs.end(), '>'), count(rhs.begin(), rhs.end(), '<')));
		}
		return res;
	}
};