Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2014-06-21

SplitStoneGame

| 23:42

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


#define vector2(TYPE) vector<vector<TYPE> >
#define vector2_cons(TYPE, A, B, DEFAULT) ((A), vector<TYPE>((B), (DEFAULT)))

class SplitStoneGame {
 public:
  string winOrLose(vector<int> number) {
    int x = 0, y = 0;
    for (int i = 0; i < number.size(); ++i) {
      if (number[i] == 1) {
        ++x;
      } else {
        ++y;
      }
    }
    dp = vector2(int) vector2_cons(int, 100, 100, -1);
    return Solve(x, y) ? "WIN" : "LOSE";
  }
 private:
  vector2(int) dp;
  bool Solve(int x, int y) {
    if (dp[x][y] != -1) return (bool)dp[x][y];
    bool res = false;
    if (x >= 2 && y >= 1) {
      res = max(res, !Solve(x - 2, y + 1));
    }
    if (x >= 1 && y >= 2) {
      res = max(res, !Solve(x - 1, y));
    }
    if (y >= 3) {
      res = max(res, !Solve(x, y - 1));
    }
    return (bool)(dp[x][y] = res);
  }
};

PalindromePermutations

| 17:23

#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 PalindromePermutations {
 public:
  double palindromeProbability(string word) {
    map<char, int> ma;
    for (int i = 0; i < word.size(); ++i) {
      ++ma[word[i]];
    }

    const double denominator = GetPatterns(ma); 

    {
      int mod2 = 0;
      for (map<char, int>::iterator it = ma.begin(); it != ma.end(); ++it) {
        mod2 += it->second % 2;
        it->second = (it->second / 2);
      }
      if (mod2 > 1)
        return 0.0;
    }

    const double numerator = GetPatterns(ma);

    return numerator / denominator;
  }
 private:
  double factorial(int n) {
    double res = 1.0;
    for (int i = 1; i <= n; ++i) {
      res *= (double)i;
    }
    return res;
  }

  double GetPatterns(map<char, int> ma) {
    int total = 0;
    for (map<char, int>::iterator it = ma.begin(); it != ma.end(); ++it) {
      total += it->second;
    }

    double res = factorial(total);
    for (map<char, int>::iterator it = ma.begin(); it != ma.end(); ++it) {
      res /= factorial(it->second);
    }

    return res;
  }
};
 |