三年目の初学者(10問目)

問題
Topcoder Single Round Match 619 Round 1 - Division I, Level One
TopCoder Statistics - Problem Statement

使用言語
C++

方針
まず、
1発でLOSEする状態を考える。初期で
{n1, n2} (数字2つ以下)
{1, 1, 1, ... , 1} (すべて1)
となるとき。

重要なのは「分割」するということなので、各numberにおいて重要なのは、2以上であるかどうか。
分割したものは、また別のnumberに加えるということなので、
{n, 1, 1, ... , 1} (n>=2)
というデータセットだとしても、次の操作で
{0, m1, m2, 1, ... , 1} (mi>=2)
となり、分割が続けられる。

WINする状況とは、Shinyの回で
{n1, n2, n3, 0, 0, ... , 0}
となる状況である。

{n1, n2, n3, n4, 0, 0, ... , 0} ではLOSE
{n1, n2, n3, n4, n5, 0, 0, ... , 0} ではWIN
.
.
.
(n>=1)

と、帰納的に奇数でWIN、偶数でLOSEであるとわかる。
って感じ。

所感
・頭やわらかゲー
・紙に書くの大切

コード

class SplitStoneGame {
    public:
    string winOrLose(vector<int> number) {
      if (number.size() <= 2 || number.size() % 2 == 0 ||
      number[*max_element(number.begin(), number.end())] == 1)
        return "LOSE";
      else return "WIN";
    }
};