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: 2024年04月26日05時41分48秒
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)

ログイン：