🐢

[鉄則A32] Game 1

2024/05/26に公開

Ruby

必勝法を求める問題。

問題を要約する

N 個の石から交互に A 個または B 個取っていく
取れなくなった方の負け

問題を理解する

1 個あって 2 or 3 個取れるとき、もう取れないのでいきなり先手の負け
2 個あって 2 or 3 個取れるとき、2 個取れば後手は取る石がないので先手の勝ち

先手必勝？

先手必勝になる理由を考えよと解説に書いてあったのでいくつかのパターンにしてみるると、たしかに先手必勝になっている。

	先	後	先	後	先
パターン1	3	2	2	×
パターン2	3	3	2	×
パターン3	2	3	2	×
パターン4	2	2	3	×
パターン5	2	2	2	2	×

パターン5は3手目に手を緩めて残り4枚に対して2枚残してわざと負けた。最善を尽すルールなのでこのようなパターンは考えなくてよい。

例1で考える

残り枚数が 0 から 8 で考えてみる。

残り	残り X 枚で手番を迎えたプレイヤーの思考	勝ち
0枚	取れないので負け
1枚	取れないので負け
2枚	2枚取れば残り0枚で勝ち	○
3枚	2枚取れば残り1枚で勝ち。3枚取れば残り0枚で勝ち	○
4枚	3枚取れば残り1枚で勝ち	○
5枚	2枚取ったら残り3枚、3枚取っても残り2枚で、負け
6枚	2枚取ったら残り4枚、3枚取っても残り3枚で、負け
7枚	2枚取れば残り5枚で勝ち。3枚取れば残り4枚で負けるので取らない	○
8枚	2枚取れば残り6枚で待ち。3枚取っても残り5枚で勝ち	○

この過程から○のついた枚数で迎えたプレイヤーが勝ちパターンに入るのがわかる。つまり最初の8枚目の手番を得た先手が必ず勝つ。

思考まとめ

2 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
3 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
どちらもだめなら自分は負ける

解説の模範解答 (AC)

51 ms

N, A, B = gets.split.collect(&:to_i)  # => [8, 2, 3]

dp = Array.new(N.next)
(0..N).each do |i|
  case
  when i >= A && dp[i - A] == :lose # 2 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
    dp[i] = :win
  when i >= B && dp[i - B] == :lose # 3 枚引いた状況に切り替えて負けならそれは相手の負けなので自分の勝ち
    dp[i] = :win
  else                              # どちらもだめなら自分は負ける
    dp[i] = :lose
  end
end

dp                                    # => [:lose, :lose, :win, :win, :win, :lose, :lose, :win, :win]

# 最初の8枚目の手番を得た先手の必勝
dp[N]                                 # => :win

puts dp[N] == :win ? "First" : "Second"

残りの何枚をインデックスにして、

	0	1	2	3	4	5	6	7	8
dp	lose	lose	win	win	win	lose	lose	win	win

できた dp 配列を参照すれば勝敗がすぐにわかる。

リファクタリング

A, B で場合分けしている部分は [A, B].any? { ... } と書ける。そうしておけば取る個数の選択肢を可変にすることもできる。それが次の課題だった。