peryaudoのTopCoder日記

EllysCandyGame

SRM606, DIV2Hard | 16:23

#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

class EllysCandyGame {
 public:
  string getWinner(vector<int> sweets) {
    const int ans = F(true, 0, 0, sweets);
    if (ans == 1) {
      return "Elly";
    } else if (ans == 0) { 
      return "Draw";
    } else {
      return "Kris";
    }
  }

  int F(bool is_elly, int escore, int kscore, vector<int>& sweets) {
    if (accumulate(sweets.begin(), sweets.end(), 0) == 0) {
      if (escore == kscore) return 0;
      return escore < kscore ? (!is_elly ? 1 : -1) : (is_elly ? 1 : -1);
    }

    int ans = -1;
    for (int i = 0; i < sweets.size(); ++i) {
      const int cur = sweets[i];
      if (cur == 0) continue;
      sweets[i] = 0;
      if (i - 1 >= 0) sweets[i - 1] *= 2;
      if (i + 1 < sweets.size()) sweets[i + 1] *= 2;

      const int curans = -F(!is_elly, is_elly ? escore + cur : escore, !is_elly ? kscore + cur : kscore, sweets);
      ans = max(ans, curans);

      sweets[i] = cur;
      if (i - 1 >= 0) sweets[i - 1] /= 2;
      if (i + 1 < sweets.size()) sweets[i + 1] /= 2;
      if (ans == 1) break;
    }

    return ans;
  }
};

よくあるゲーム木(?)全探索。Drawがあるのでboolでは結果を持てないことに注意。

EllysNumberGuessing

SRM606, DIV1Easy | 00:12

#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 EllysNumberGuessing {
public:
	bool valid(long long x) { return 1LL <= x && x <= 1000000000; }
	int getNumber(vector<int> guesses, vector<int> answers) {
		if (guesses.size() == 1) {
			const long long a = (long long)guesses[0] + answers[0];
			const long long b = (long long)guesses[0] - answers[0];
			if (valid(a) && valid(b)) return -1;
			if (valid(a)) return a;
			if (valid(b)) return b;
			return -2;
		}


		vector<pair<long long, long long> > sorted;
		for (int i = 0; i <  guesses.size(); ++i) {
			sorted.push_back(make_pair(guesses[i], answers[i]));
		}

		sort(sorted.begin(), sorted.end());

		int res = -2;
		for (int i = 0; i < sorted.size() + 1; ++i) {
			vector<long long> estimated(sorted.size());
			for (int j = 0; j < i; ++j) {
				estimated[j] = sorted[j].first + sorted[j].second;
			}
			for (int j = i; j < sorted.size(); ++j) {
				estimated[j] = sorted[j].first - sorted[j].second;
			}

			bool allEqual = true;
			for (int i = 0; i < estimated.size(); ++i) {
				if (estimated[i] != estimated[0]) {
					allEqual = false;
					break;
				}
			}

			if (allEqual && valid(estimated[0])) {
				if (res != -2) return -1;
				else res = (int)estimated[0];
			}
		}
		return res;
	}
};

Score: 148.93 / 250 (1331 secs)

するめの過去問を解くのを再開していこうと思います…