[Atcoder] K - Stones [DP まとめコンテスト]

問題 : dp-k Stones

結論

dp[x] := x個の石でゲームして、最初に行動するプレイヤーが勝つことができるか

def getInts():
    return map(int, input().split())

def getIntsArray():
    return [int(x) for x in input().split()]

N, K = getInts()
choices = getIntsArray()
dp = [False] * (K + 1)
for i in range(K):
    for choice in choices:
				if i + choice <= K:
						dp[i + choice] = dp[i + choice] or not dp[i]
if dp[K]:
    print("First")
else:
    print("Second")

思考順序

何を状態として保持するかを考えました。

まずは

• dp[x] := x個以上石を取る最短の手順
• dp[x+a_1], dp[x+a_2]..., dp[x+a_n]への遷移を考える
• 最終的にdp[K] (mod2)を答える

実装例

INF = float("inf")
dp = [INF] * (K + 1)
for i in range(K):
    for choice in choices:
        if i + choice <= K:
            dp[i + choice] = min(dp[i + choice], dp[i] + 1)

turns = dp[K]
if turns % 2 == 0:
    print("Second")
else:
    print("First")

しかし、このdpテーブルはこのゲームのルールを正確に反映できていません。

たとえば

K = 4, choices = (2, 3)のとき
石の数は、先手が勝つように4 -> 1 と遷移するべきですが、dp[4] = 2で表現される取り方は 4 -> 2 -> 0です。先手がわざわざ後手が勝つような取り方をしてしまっています。

各プレイヤーの最適行動は？

では、プレイヤーにとって最適な行動とは何でしょうか？

具体的な数字で考えるのが本質をとらえる近道です。

具体例で考えてみます。

K = 20, choices = (1,2,3)

Kが4nなら必ず後手が勝つのがわかります。

相手と合わせて4になるように取り続ければいいです。

相手との取る個数の和で考えるのがよさそうでしょうか？しかし、これはすぐに否定されます。

必ず一定の和に落とすことが難しいです。 ex) (1, 3, 7)

他の例も続けて見ましょう

choices = (2,3)

K = 4のとき

4 -> 1 でFirst

K = 5のとき

5 -> 2 -> 0
5 -> 3 -> 0でSecond

K = 7のとき

7 -> 4 -> 1 First
7 -> 5 こうすると自分が負けるから選ばない

上記の例を見ると、プレイヤーは自分が詰んでしまうような選び方はできない
ということがわかります。
逆に言うと、相手を詰ませるように選ぶのが最適行動です。当たり前ですが…
しかもこの例における、K=4やK=5のようにどう選んでもどちらが勝つか決定してしまうゾーンが存在します。

すると、持つべき状態は非常に単純ですが
dp[x] := x個の石があるときに先手が勝てるかどうか Boolean
と定義するのがよさそうです。

また、K = 7のときを見てわかるように、このdpテーブルでは、先手が勝つならそれを優先するので、
dp[i+choice]への遷移を考えるとき
dp[i + choice] = dp[i + choice] or not dp[i]とすべきです

計算量

計算量はサイズKのdpテーブルの各状態から、N個の選択肢の数だけ遷移させるので

O(NK)

です。今回は10**7で収まっています。