AtCoder Educational DP Contest K問題解いてみた

今回の問題

問題文

$N$ 個の正整数からなる集合 $A={a_1, a_2, \ldots, a_N}$ があります。
太郎君と次郎君が次のゲームで勝負します。

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

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

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

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n,k;
    cin >> n >> k;
    int alist[n];
    for (int i = 0; i < n; i++) {
        cin >> alist[i];
    }
    int dp  [k+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i <= k; i++) {
        for(int j = 0;j<n;j++){
            if(i - alist[j] >= 0){
                if(dp[i - alist[j]] == 0){
                    dp[i] = 1;
                    break;
                }
            dp[i] = 0;
            }
        }
    }
    if(dp[k] == 1){
        cout << "First" << endl;
    }else{
        cout << "Second" << endl;
    }
    return 0;
}

解説

残りi個の時自分の番になったら勝てるかを保存しておく。i-1番目まで定まってたらi番目が求められる。もし、i-取れる石番目に負けが一個でもあったら勝ちになり、どれも勝ちなら負けになる。

太郎君が勝てるかではなく、手番の人が勝てるかというふうにするのがみそ。このせいでちょっとこんがらがった。