結果
問題 | No.102 トランプを奪え |
ユーザー |
![]() |
提出日時 | 2016-09-13 21:46:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,156 bytes |
コンパイル時間 | 2,015 ms |
コンパイル使用メモリ | 185,748 KB |
実行使用メモリ | 20,224 KB |
最終ジャッジ日時 | 2024-11-17 05:06:04 |
合計ジャッジ時間 | 4,543 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; namespace { typedef double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; auto i = vs.begin(); os << "[" << *i; for (++i; i != vs.end(); ++i) os << " " << *i; return os << "]"; } template<class T> istream& operator>>(istream& is, vector<T>& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } vector<int> N; int S; void input() { N.resize(4); cin >> N; S = 0; for (int i = 0; i < 4; i++) S += N[i]; } const int INF = 1<<28; map<vector<int>, map<int, int>> cache; int dfs(vector<int>& xs, int tscore, int t) { if (cache.count(xs) && cache[xs].count(tscore)) { return cache[xs][tscore]; } int sum = 0; for (int i = 0; i < 4; i++) sum += xs[i]; int jscore = S - sum - tscore; int nscore = -1; // 譛濶ッ謇九r縺ィ縺」縺溘→縺阪・莉頑焔逡ェ縺ョ莠コ縺ョ轤ケ謨ー int flag = false; for (int i = 0; i < 4; i++) { if (xs[i] == 0) continue; flag = true; for (int j = 1; j <= min(3, xs[i]); j++) { xs[i] -= j; if (t) { nscore = max(nscore, dfs(xs, tscore + j + (xs[i] == 0 ? (jscore + 1) / 2 : 0), !t)); } else { int z = dfs(xs, tscore - (xs[i] == 0 ? (tscore + 1) / 2 : 0), !t); nscore = max(nscore, S - z); } xs[i] += j; } } return cache[xs][tscore] = (flag ? (t ? nscore : S - nscore) : tscore); } void solve() { int t = dfs(N, 0, 1); int j = S - t; if (t == j) { cout << "Draw" << endl; } else if (t > j) { cout << "Taro" << endl; } else { assert(t < j); cout << "Jiro" << endl; } } } int main() { input(); solve(); return 0; }