TopCoder SRM 619 Div1 Easy SplitStoneGame

問題概要

N要素の数列で次の操作を交互に繰り返す.

  • 2以上の要素xを選んで,和がxの正の2数a,bに分ける.
  • x以外に要素2つをp,qとし,p+=x,q+=bする.

この操作ができなくなったほうが負け.先手が勝つならWINを,負けるならLOSEを返す

解法

xは2以上の要素からしか選ぶことができないし,それさえ満たしていれば操作できる回数は変わらないためどれを選んでも良い.
逆に,p,qはできるだけ1の要素から選びたい.2以上の要素が増えると操作回数は増えるからである.またこれも1であればどれを選んでもよい.
数列の要素のうち,2以上のものの個数をt,1のものの個数をuとする.
f(t,u)=(2以上がt個,1がu個ある盤面が渡されたとき勝てるか)とすると,
f(t,u) = 
\begin{cases}
false & (t+u<3 \lor t=0) \\
!f(t-1,0) & (u=0)\\
!f(t,0) &(u=1)\\
!f(t+1,u-2) &(otherwise)
\end{cases}
となる.これを再帰で解けばよい.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;

class SplitStoneGame{
public:
    bool dfs(int p,int q){
        if(p+q<3){
            return false;
        }
        if(!p){
            return false;
        }
        if(!q){
            return !dfs(p-1,0);
        }else if(q==1){
            return !dfs(p,0);
        }else{
            return !dfs(p+1,q-2);
        }
    }
    string winOrLose(vi vec){
        int n=vec.size();
        int p=0,q=0;
        REP(i,n){
            if(vec[i]>1){
                p++;
            }else{
                q++;
            }
        }
        return dfs(p,q)?"WIN":"LOSE";
    }
};