#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では結果を持てないことに注意。
#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)
するめの過去問を解くのを再開していこうと思います…