Hatena::Grouptopcoder

peryaudoのTopCoder日記

2016-04-26

EmployManager

| 15:58

#include <iostream>
#include <vector>
#include <string>

using namespace std;
using ll = long long;

class EmployManager {
 public:
  int maximumEarnings(vector<int> value, vector<string> earning) {
    ll se = 0;
    int ans = Eval(value, earning, se);
    bool changed = true;
    while (changed) {
      changed = false;
      ll curse = se;
      for (ll i = 0; i < value.size(); ++i) {
        if (se & (1LL << i)) continue;
        const int cur = Eval(value, earning, se | (1LL << i));
        if (cur > ans) {
          changed = true;
          curse = se | (1LL << i);
          ans = cur;
        }
      }
      se = curse;
    }
    return ans;
  }

  int Eval(const vector<int>& value, const vector<string>& earning, ll se) {
    int ans = 0;
    for (ll i = 0; i < value.size(); ++i) {
      if (se & (1LL << i)) {
        ans -= value[i];
      }
    }
    for (ll i = 0; i < value.size(); ++i) {
      for (ll j = i + 1; j < value.size(); ++j) {
        int cost = earning[i][j] - '0';
        if ((se & (1LL << i)) && (se & (1LL << j))) {
          ans += cost;
        } else if (!(se & (1LL << i)) && !(se & (1LL << j))) {
          ans -= cost;
        }
      }
    }
    return ans;
  }
};

貪欲提案おじさん

(証明できて)ないです

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