TopCoder SRM619 DIV1 EASY (250pt)
Problem Statement
最初,$N$ 個の山があって,$k$ 番目の山は $A_k$ 個の石からできている. $2$ 人でゲームを行う.打つ手がなくなったら負け.先手必勝か後手必勝かを判定する問題. $1$ 人ずつ順番に以下の行動1~3.を行う.
最初のターンが無事こなせる(つまり,山の数が $3$ つ以上で,$2$ 個以上石がある山がある)ならば,その後は合体させた山は $2$ つ以上石があるので,$2$ つ以上石がある山が選べなくて負けることはない.
つまり,最初のターンが無事こなせるならば,つつがなく進行し,山の数が $1$ つずつ減っていき,$2$ つしか山がなくなったら行動できなくなる.
よって,山の数の偶奇で勝敗が決る.
石の数が $2$ 個以上の山がいくつあるか,石の数が $1$ 個の山がいくつあるか,を状態としてDPしても良い.
// #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";
}
}
// #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月27日07時45分22秒
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)