SRM606 Div2 Hard "EllysCandyGame"
問題
TopCoder Statistics - Problem Statement
訳
エリーとクリスは次のようなゲームで遊んでいる。いくつかの箱が一列に並んでいる。この箱にはキャンディが入っている(入ってない場合もある)。実は、彼女たちはそれぞれの箱に、いくつキャンディが入っているか、正確に把握している。その情報はint[] sweetsとして、あなたに与えられる。
まずはエリーのターンで、交互にターンが回ってくる。1ターンで、プレイヤーはキャンディの入っている箱を選び、その箱の全てのキャンディを取って自分のものにする。その後、両隣の箱のキャンディを2倍にする。例えば、5つの箱があって、キャンディの数が{20, 50, 70, 0, 30}とする。0番目の箱を選ぶと{0, 100, 70, 0, 30}になる。1番目の箱を選ぶと{40, 0, 140, 0, 30}になる。また、3番目の箱はキャンディが入っていないので、選ぶことはできない。
全ての箱のキャンディがなくなったらゲーム終了となる。そのとき、キャンディを多く持っていたほうが、このゲームの勝者となる。
2人の少女が互いに最善を尽くしたとき、どちらが勝者となるかを返せ。引き分ける場合は"Draw"を返せ。
制約
1 <= 箱の数 <= 10
0 <= それぞれの箱のキャンディの数 <= 1000
考えたこと
箱は高々10個なので、シミュレートすると10!=300万ぐらいとなるため、シミュレート可能。
ターン制のゲームで勝者を考えるときは、次のようにする。
ターンが回ってきたときに、プレイヤーAがN通りの行動がとれるとする。 N通りのうち、1つでも勝てるものがあれば、プレイヤーAの勝ちとなる。 N通りのうち、勝てるものがない場合、プレイヤーAの負けとなる。
今回は、引き分けが存在するので、以下のようにする。
ターンが回ってきたときに、プレイヤーAがN通りの行動がとれるとする。 N通りのうち、1つでも勝てるものがあれば、プレイヤーAの勝ちとなる。 勝てるものがない場合、1つでも引き分けるものがあれば、引き分けとなる。 引き分けにすることもできなければ、プレイヤーAの負けとなる。
ソースコード
int N; vector<int> C; class EllysCandyGame { public: // ゲームの結果を返す // 1...エリーの勝ち // 0...引き分け // -1...クリスの勝ち int solve(bool isElly, int E, int K){ int res; bool isEnd = true; if (isElly) { // エリーのターン res = -1; for (int i = 0; i < N; i++){ if (0 < C[i]){ isEnd = false; int m = C[i]; E += m; C[i] = 0; if (0 <= i - 1) C[i - 1] *= 2; if (i + 1 < N) C[i + 1] *= 2; // なるべくエリーが有利になるステータスにする res = max(res, solve(!isElly, E, K)); if (0 <= i - 1) C[i - 1] /= 2; if (i + 1 < N) C[i + 1] /= 2; E -= m; C[i] = m; } } } else{ // クリスのターン res = 1; for (int i = 0; i < N; i++){ if (0 < C[i]){ isEnd = false; int m = C[i]; K += m; C[i] = 0; if (0 <= i - 1) C[i - 1] *= 2; if (i + 1 < N) C[i + 1] *= 2; // なるべくクリスが有利になるステータスにする res = min(res, solve(!isElly, E, K)); if (0 <= i - 1) C[i - 1] /= 2; if (i + 1 < N) C[i + 1] /= 2; K -= m; C[i] = m; } } } // キャンディが入っている箱が1つもなければゲーム終了 if (isEnd){ if (K < E) return 1; if (E < K) return -1; return 0; } return res; } string getWinner(vector <int> sweets) { N = sweets.size(); C = sweets; int res = solve(true, 0, 0); if( res == 1 ) return "Elly"; if (res == -1) return "Kris"; return "Draw"; } };