ゲームDPってなんぞ

動的計画法の使い方の一つで、主にゲームの勝敗や得点等の状態を管理するもの。 例題を通して考え方を身につけましょう。

例題( EDPC K - Stone )

N $個の正整数からなる集合 $A={$a_1,a_2,…,a_N$}があります。

太郎君と次郎君が次のゲームで勝負します。

最初に、$K$個の石からなる山を用意します。 二人は次の操作を交互に行います。 先手は太郎君です。

A $の元 $x をひとつ選び、山からちょうど $x$ 個の石を取り去る。

先に操作を行えなくなった人が負けです。 二人が最適に行動すると仮定したとき、どちらが勝つかを判定してください。

$1≤N≤100 $
$ 1≤K≤10^5$
$1≤a_1<a_2<⋯<a_N≤K $

いかに考えるか

$A=${$2,3$} K=4のとき下図のようなゲームフローとなる(3の場合はたどり着けないので実際には存在しないが)

勝敗を調べようと考えると、図の下から上の向きに探索を進めるのが自然。

0の時、負け
1の時、負け
2の時、0にできるから勝ち（0で負けるという情報があって初めて勝ちを判断できる）
3の時、1にできるから勝ち（同様）
...みたいな感じで(4の時は後述)

各ノードに対して、その盤面での勝敗を決定していくことで解くことができそうですね。

$dp$[$i$]: $i$ 個あるとき勝てる状況か？
これをiが小さい順に更新していきます。
この方法では、今どっちの手順やねん！とか考えなくてよいのがいいですね。

上の図の4の時のように、複数の状態に遷移するものの勝敗を考えてみましょう。
今、あなたが空白の状態にいるとして、どちらに遷移するでしょうか。

「勝ち」に遷移してしまうと、手番が交互なので相手が勝ってしまいます。

「負け」に遷移すれば、相手が負けるので自分が勝ちます。

つまり、遷移先に「負け」が一つでもある場合は勝ちになるということですね。

「勝ち→空白」「負け→空白」という順で探索することになる場合、空白のノードは、最初は勝ち（探索元）の逆で負けになり、次に勝ちに更新されます。

「負け→空白」「勝ち→空白」という順で探索することになる場合、空白のノードは、最初は負け（探索元）の逆で勝ちになり、次に負けに更新されず勝ちのままです。
つまるところ、
dp[i+a[j]]が勝ちでない時、dp[i+a[j]]=dp[i]の逆
というわけです。

コード

/**** main function ****/
ll n,k;
vector<ll> a;
ll stone[100001];//石がi個あるとき、そこから勝つかどうか 1:かち / -1:まけ
 
int main(){
  cin>>n>>k;
  for(ll i=0;i<n;i++){
    ll aa;
    cin>>aa;
    a.push_back(aa);
    stone[aa]=1;
  }
  stone[0]=-1;
  for(ll i=0;i<=k;i++){
    if(stone[i]==0){//遷移先がないので負け
      stone[i]=-1;
      for(ll j=0;j<n;j++){
        if(a[j]+i<=k){
          stone[a[j]+i]=1;
        }
      }
    }else if(stone[i]==1){//勝ちから
      for(ll j=0;j<n;j++){
        if(a[j]+i<=k&&stone[a[j]+i]==0){//勝ちを負けに更新しないように
          stone[a[j]+i]=-1;
        }
      }
    }else{//負けから
      for(ll j=0;j<n;j++){
        if(a[j]+i<=k){
          stone[a[j]+i]=1;
        }
      }
    }
  }
  if(stone[k]==1){
    cout<<"First"<<endl;
  }else{
    cout<<"Second"<<endl;
  }
}

あとがき

案外すんなり書けてビビっている。
EDPCのLもゲームDPなので挑戦してみるとよいです EDPC L - Deque
範囲が絡むDPが特に苦手なきがするのでEDPCで練習せななぁ
(dp[i]:iまでにうんぬん,みたいなやつ)