「負け状態」と「勝ち状態」の非対称な関係
自分の手番の状態 k における状態価値関数の値を dp[k] とします。
・・・状態価値関数って何？？？？
ゲームに勝利した時の得点を 1 として、この後、ゲームを進めていって最終的に得られる得点の事。（だとしておきます、ここでは。もう少し厳密な説明は、次の記事で。）
たとえば、自分の手番の状態「k」において、自分の負けが確定した状態（このゲームの場合は、打つ手がなくなった状態）は、
・dp[k] = 0
になります。一方、この負けが確定した状態の一歩手前の状態 k は、相手の負けが確定した状態、つまり、自分の勝ちが確定した状態なので、
・dp[k] = 1
となります。
逆の見方をすると、一般に、ある状態 k に対して、
・移動可能な次の状態 k' の中に dp[k'] = 0 となるものがあれば、dp[k] = 1 ---- (1)
・移動可能な次の状態 k' のすべてに対して、dp[k'] = 1 であれば、dp[k] = 0 ---- (2)
と決まります。
これ、(1) と (2) で条件が微妙に非対称になっている点に注意してください。どうがんばっても相手に「勝ち状態」を譲らないといけないのが (2) の「負け状態」なのです。また、もう一つ重要なポイントは、(2) については、状態 k から移動可能なすべての状態 k' について dp[k'] が確定していないと、dp[k] を確定することができないという点です。
変化が一方向のゲームの場合
という状況を考えると、一般には、どういう順番で dp[ ] を確定させていけばよいかが悩ましいのですが、今回のゲームでは、残りの石の数を状態 k に対応させると「k は必ず減る方向に変化する」という条件があるので、dp[k] を決めるためには、dp[0] 〜 dp[k-1] が決まっていれば十分です。つまり、k = 0, 1, 2, 3, ... という順番に決めればOKです。
というわけで、あっさり完成したのがこちらです。
import sys def main(f): N, K = list(map(int, f.readline().split())) A = list(map(int, f.readline().split())) dp = [None] * (K+1) for i in range(A[0]): # 石の数が「取れる石の数」の最小値 A[0] 未満は負けが確定 dp[i] = 0 for k in range(A[0], K+1): for a in A: if k - a < 0: continue if dp[k - a] == 0: # 「負け状態」に遷移できれば「勝ち状態」 dp[k] = 1 break if dp[k] == None: # さもなくば（「勝ち状態」にしか遷移できない）「負け状態」 dp[k] = 0 if dp[K] == 1: # ゲーム開始状態が「勝ち状態」ならプレーヤー1の勝ち print('First') else: print('Second') main(sys.stdin)
おまけ：Grundy 数について
今回の問題に限らず、一般にこの手のゲームの問題では、
・状態 k から遷移可能なすべての状態 k' について dp[k'] がわかっていれば、dp[k] が決まる
というルールがありますので、まずは、状態遷移を有効グラフに描いて、どの順番に dp[ ] を決めていけばよいかを整理するのがよいでしょう。
また、
・負けが確定した状態 k に対しては、dp[k] = 0
・移動可能な次の状態 k' の中に dp[k'] = 0 となるものがあれば、dp[k] = 1
・移動可能な次の状態 k' のすべてに対して、dp[k'] = 1 であれば、dp[k] = 0
というルールを一般化した、「Grundy 数」と呼ばれるものがあります。これは次のルールで決まります。
・負けが確定した状態 k に対しては、dp[k] = 0
・移動可能な次の状態 k' のすべてに対する dp[k'] を集めたリストを A として、dp[k] = (A に含まれない最小の非負整数値)
少し考えると分かるように、dp[k] = 0 は負け状態で、dp[k] > 0 は勝ち状態になります。
今回の問題であれば、わざわざ Grundy 数を使う必要がありませんが、実は、
・複数の山を並列にプレイする（自分の手番では、どれか１つの山に対する操作を行い、どの山に対しても操作できなくなったら負け）
という特殊な問題では、各山の初期状態の Grundy 数によって、全体の勝敗を求めることができます。（各 Grundy 数のビット単位の xor を計算して、0 であれば後手の必勝）
このような問題の例は、こちらになります。
