WARush

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

SRM619 Div1 Easy "SplitStoneGame"

問題

TopCoder Statistics - Problem Statement

シャイニーはゲームが好きだ。彼女のお気に入りのゲームは小石を使ったゲームである。今日、彼女は彼女の友達であるルーシーとゲームで遊んでいた。

始め、小石でできたN個の山がある。あなたはN個の要素を持つint[] numberが与えられる。number[i]はi番目の山の小石の数を表す。

プレイヤーは交互にターンが回ってくる。シャイニーは先行である。それぞれのターンで、手番であるプレイヤーは下記のような行動を取らなくてはならない。

1. 少なくとも2つの小石がある山 X を選ぶ。
2. Xの小石をA, Bの2つに分ける。(A, Bとも0個以外であれば、任意の数をとれる)
3. 2つの山Y, Zを選ぶ。(YとZはXを除いた、1つ以上の小石を持つ違う山でなくてはならない)
4. Aの小石をYへ追加し、Bの小石をZに追加する。

例えば、山が{1, 2, 50}だとすると、プレイヤーは下記のような行動を取る。

1. 小石の数が50の山を選び、Xとする。
2. 25ずつに分ける
3. 他の2つの山を選び({1, 2}となる)、YとZとする。
4. AをYに、BをZに加え、最終的に{26, 27}となる。

行動が取れなくなったプレイヤーが負けとなる。お互い最善を尽くしたとして、シャイニーが勝つか負けるかを返せ。

制約

1 <= number.size <= 50
1 <= number[i] <= 50


考えたこと

負ける条件として、山が2つ以下となるか、小石が2つ以上の山が存在しない、の2つになる。もし小石が2つ以上の山が1つでも存在したとすると、どのような行動をとっても小石が2つ以上の山が必ずできてしまう。各ターンで1つずつ山が少なくなっていくため、初期の山の数の偶奇で勝ち負けが決まる。


ソースコード

class SplitStoneGame {

    public:

    string winOrLose(vector <int> number) {
        int n = number.size();

        if (n < 3) return "LOSE";

        bool two = false;
        for (int i = 0; i < n; i++) {
            if (number[i] >= 2) two = true;
        }
        
        if (!two) return "LOSE";

        return n % 2 == 1 ? "WIN" : "LOSE";
    }
};