WARush

SRMの結果とか、解けた問題のコードを書いていきます

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