[Python] Educational DP Contest K – Stones

問題

K – Stones

参考

AtCoderDPまとめコンテスト K問題 「Stones」

例題 2. EDPC K 問題 – Stones　〜 石取りゲームの一般化 〜

回答

import sys
# input処理を高速化する
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    lst_a = list(map(int, input().split()))

    # 石の個数が残りi個の局面で勝ちTrue 負け False　
    dp = [False] * (K+1)

    for i in range(1, K+1):
        for j in range(N):
            if i - lst_a[j] >= 0:
                dp[i] |= not(dp[i - lst_a[j]])
    
    if dp[K]:
        print('First')
    else:
        print('Second')

main()