コインゲーム（動的計画法）

問題

NancyとTomが次のようなゲームをします。

$ k $ 個の数字 $ a_1, a_2, …, a_k $ が決まっています。

最初に $ x $ 枚のコインがあって、NancyとTomが交互にコインを取っていきます。

一度に取るコインの枚数は $ a_1, a_2, …, a_k $ のいずれでないといけません。

最後のコインを取ったほうが勝ちとなります。

最初はNancyの番で、両者とも最善を尽くすとした場合、どちらが勝つでしょうか。

（$ a_1, a_2, …, a_k $ の中には必ず $ 1 $ が含まれています。）

[制約]

🔹$ 1 \leqq x \leqq 10000 $
🔹$ 1 \leqq k \leqq 100 $
🔹$ 1 \leqq a_i \leqq x $

解法・ソースコード

$ j $ 枚のコインがある状態で順番が回ってきたときに勝てるのかどうかを考えます。

🔹最後のコインをとったら勝ちというのは0枚で自分にまわってきたら負けと考えても同じです。
　つまり、$ j=0 $ ならば負けとなります。

🔹ある $ i　(1 \leqq i \leqq k) $ に対し、$ j - a_i $ 枚が負けならば、$ j $ 枚は勝ち
　（ $ j $ 枚で回ってきたら、$ a_i $ 枚とれば相手は負ける ➡ 自分が勝つ）

🔹すべての $ i　(1 \leqq i \leqq k) $ に対し、$ j - a_i $ 枚が勝ちならば、$ j $ 枚は負け
　（どのような取り方をしても、必ず相手が勝つ ➡ 自分はどうやっても負ける）

上記をもとに、動的計画法を使って小さい $ j $ から順に勝ち負けを計算していき、$ x $ 枚が勝ちであるか負けてであるかをみれば問題が解けることになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#--------- 入力例1 ----------
x = 9
coins = [1, 4]
#--------- 入力例2 ----------
# x = 10
# coins = [1, 4]
#----------------------------
k = len(coins)      # 選べるコイン数のパターン数

# 動的計画法用の変数
#   キー：コイン数
#   バリュー：Nancyの勝ち(True)、Tomの勝ち(False)
memo = {}

for j in range(1, x + 1):   # コイン数分ループ
    memo[j] = False
    for coin in coins:      # 選べるコインごとのループ
        res = coin <= j and memo.get(j - coin, False) == False
        memo[j] = memo[j] or res    # 論理和（どちらかがTrueだったらTrue）
print(memo)
print('解：', 'Nancyの勝ち' if memo[x] else 'Tomの勝ち')

[実行結果（入力例1）]

{1: True, 2: False, 3: True, 4: True, 5: False, 6: True, 7: False, 8: True, 9: True}

解： Nancyの勝ち

[実行結果（入力例2）]

{1: True, 2: False, 3: True, 4: True, 5: False, 6: True, 7: False, 8: True, 9: True, 10: False}

解： Tomの勝ち