TopCoder SRM619 DIV1 EASY - SplitStoneGame

Source

TopCoder SRM619 DIV1 EASY (250pt)
Problem Statement

問題概要

最初,$N$ 個の山があって,$k$ 番目の山は $A_k$ 個の石からできている. $2$ 人でゲームを行う.打つ手がなくなったら負け.先手必勝か後手必勝かを判定する問題. $1$ 人ずつ順番に以下の行動1~3.を行う.

  1. $2$ 個以上の石を含む山を $1$ つ選び,$2$ つの空でない山に分割する.新しい山の石の数は自由に分割して良い.新しい山を$x,y$と呼ぶ
  2. 新しくできた山 $x,y$ 以外の山を $2$ つ選ぶ.選んだ山を $s,t$ と呼ぶ
  3. 山 $x$ と $s$ を合体させて $1$ つの山にし,$y$ と $t$ を合体させて $1$ つの山にする

解法

最初のターンが無事こなせる(つまり,山の数が $3$ つ以上で,$2$ 個以上石がある山がある)ならば,その後は合体させた山は $2$ つ以上石があるので,$2$ つ以上石がある山が選べなくて負けることはない.
つまり,最初のターンが無事こなせるならば,つつがなく進行し,山の数が $1$ つずつ減っていき,$2$ つしか山がなくなったら行動できなくなる.
よって,山の数の偶奇で勝敗が決る.
石の数が $2$ 個以上の山がいくつあるか,石の数が $1$ 個の山がいくつあるか,を状態としてDPしても良い.

C++によるスパゲッティなソースコード

// #includeなどは略しています
class SplitStoneGame {
public:
string winOrLose(vector <int> in) {
  sort(in.begin(), in.end());
  if(in.size() <= 2 || in.size()%2==0 || in[in.size()-1]==1) return "LOSE";
  return "WIN";
}

}

C++によるスパゲッティなソースコード(DP解法)

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int dp[1000][1000];

int solve(int one, int many){
  int i, j, k;
  int res = 0;

  if(dp[one][many] >= 0) return dp[one][many];

  if(many >= 1 && one >= 2) res |= 1 - solve(one-2, many-1+2);
  if(many >= 2 && one >= 1) res |= 1 - solve(one-1, many-2+2);
  if(many >= 3 && one >= 0) res |= 1 - solve(one-0, many-3+2);

  return dp[one][many] = res;
}

class SplitStoneGame {
public:
string winOrLose(vector <int> in) {
  int i, j, k;
  int one, many;

  rep(i,1000) rep(j,1000) dp[i][j] = -1;
  one = many = 0;
  rep(i,in.size()){
    if(in[i]==1) one++;
    else         many++;
  }

  if(solve(one,many)) return "WIN";
  return "LOSE";
}

}

Current time: 2017年07月23日15時32分18秒
Last modified: 2014年05月10日03時24分57秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM619 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: