めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

K - Stones の解説

何の話かと言うと

atcoder.jp

この問題をネタにして、対戦ゲーム(マルコフ決定過程)の基本的な考え方を説明します。

「負け状態」と「勝ち状態」の非対称な関係

自分の手番の状態 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)

atcoder.jp