SRM 619 DIV1 Easy - SplitStoneGame (××)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13113&rd=15852

・積み重ねられた石の山が複数存在する。
・それぞれの山について、あらかじめいくつ石が積み重ねられているかわかっている。
・現在の石の山から1つ選んで2つに分け、また別の山を2つ選んで振り分ける。
・2つに分ける方法として、片方が0にならなければどのように分けてもよい。
・上記のゲームを2人で交互に行い、分けられなくなった場合は負けになる。
・このとき、最初のプレイヤーが勝つときはWIN,、負けるときはLOSEを返す。

解き方


・サンプルと問題文からダメなパターンをみてみる。
・まず、石の山が2つ以下の場合は必ず負ける。
・また、全ての石の山が1のときは動かせないので必ず負ける。

・それ以外のときとして、山が3つの時は必ず2つにできるので勝つ。
・山が4つのときは必ず3つ→2つになるので負けてしまう。
・よって、最初が全て1でなければ山を一つずつ必ず減らすことができる。

・まとめると、石の山が2つ以下またはすべて1のときは負け、
 そうでないときは山の数が奇数のときは勝ち、偶数のときは負ける。
 

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class SplitStoneGame {

public: string winOrLose(vector<int> number) {
int n=number.size();
int flag=1;
FORE(i,0,n)if(number[i]!=1)flag=0;

if(n<3||flag)return "LOSE";

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

};
このエントリーをはてなブックマークに追加