Educational DP Contest / DP まとめコンテスト [ K - Stones ] https://atcoder.jp/contests/dp/tasks/dp_k

edpc_k.py

'''
[問題]
https://atcoder.jp/contests/dp/tasks/dp_k

[解説]
https://blog.hamayanhamayan.com/entry/2019/01/09/002200
dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態）
後退解析の基本は「遷移先がすべて勝ち状態なら負け状態。遷移先に1つでも負け状態があれば勝ち状態」である。
あるdp[k]について、遷移先は100通りあるので、このすべてを見て、負け状態が1つでもあれば勝ち状態にする。
注意すべきなのは、遷移することができない（遷移先が無い）場合は、操作を行えないということなので負け状態とすること。

https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000

[参考]
元 (数学)
https://ja.wikipedia.org/wiki/%E5%85%83_(%E6%95%B0%E5%AD%A6)

https://atcoder.jp/contests/dp/submissions/24745177
https://atcoder.jp/contests/dp/submissions/24730634
https://atcoder.jp/contests/dp/submissions/24598732

'''

# はまやん氏のコードをPythonコンバート
# 後退確認
import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N, K = map(int, input().split())
A = list(map(int, input().split()))

# 石の数K分のdp配列を用意する
# dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態）
dp = [2] * (K+1)    # デバッガで動きが確認しやすいように0,1以外で初期化してみる

# 0 - Kまでループ
# 先手が行動して勝てるか？を判定するループ
# Kよりも小さいk個の石山でシミュレーションして、先手が勝ちかを調べる。
# kの値を1ずつ大きくなるにしたがって、小さい山での結果はわかっていて、その結果が使える
for k in range(K+1):

    lose = 0
    cnt = 0

    # k固定で、Aの元（属する要素）をループ
    for a in A:

        if 0 <= (k - a):
            # k-aが行動可能
            cnt += 1
            if dp[k - a] == 0:
                # 遷移先に行ったとき、そこの手番を次に行う相手（つまり後手）は負け
                lose += 1

    if cnt == 0:
        # 先手行動できず。先手負けの後手勝ち
        dp[k] = 0
    elif 0 < lose:
        # 先手の勝ち
        dp[k] = 1
    else:
        # 後手の勝ち
        dp[k] = 0

if dp[K] == 1:
    # dp[K]のゲーム初期状態が1なら、先手の勝ち
    print("First")
else:
    print("Second")