Stones [Educational DP Contest / DP まとめコンテスト K]

https://atcoder.jp/contests/dp/tasks/dp_k

前提知識

• 後退解析

解説

https://atcoder.jp/contests/dp/submissions/3948285

ゲーム問題のテクとして後退解析がある。
この後退解析をDPっぽくやる手法がある。
dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態）
後退解析の基本は「遷移先がすべて勝ち状態なら負け状態。遷移先に1つでも負け状態があれば勝ち状態」である。
あるdp[k]について、遷移先は100通りあるので、このすべてを見て、負け状態が1つでもあれば勝ち状態にする。
注意すべきなのは、遷移することができない（遷移先が無い）場合は、操作を行えないということなので負け状態とすること。

int N, K, A[101], dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
 
    rep(k, 0, K + 1) {
        int lose = 0, cnt = 0;
        rep(i, 0, N) if (0 <= k - A[i]) {
            cnt++;
            if(!dp[k - A[i]]) lose++;
        }
        if (cnt == 0) dp[k] = 0;
        else if (0 < lose) dp[k] = 1;
        else dp[k] = 0;
    }
 
    if (dp[K]) printf("First\n");
    else printf("Second\n");
}