🐢

[鉄則A34] Game 3 (Grundy数)

2024/05/30に公開

Ruby

Grundy 数問題。

問題を要約する

いくつかの山がある
どれかの山から石を X or Y 個取っていく
山から石を取れなくなったら負け

ニムに似ているが「1つ以上」のルールが「X or Y 個」に変わっている。

mex とは？

mex = Minimum Excluded
集合に含まれていない最小の非負整数のこと

たとえば [0, 2] だと 1

具体的な mex の求め方

set = [0, 2]

から 1 を求めるには、

transit = set.each_with_object([]) { |e, m| m[e] = true }
transit.find_index { |e| !e } || transit.size  # => 1

とするのでよさそう。

例1での考え方

5 個と 8 個の山があり、2 or 3 個取れる

なのでまず Grundy 数を求める。Grundy 数は、

貰うDPの要領で前から埋めていく
mex のことでもある
その集合は 2 個前と 3 個前の両方の値になる

で求まる。

当初「2 or 3 個」とあるのに釣られて「2 個前と 3 個前のどちらか」と考えてしまって混乱した。or とあっても mex の集合には両方を含める。ここだけ間違わなければ頭ですぐに表を作れるようになる。

	0	1	2	3	4	5	6	7	8
2 or 3	0	0	1	1	2	0	0	1	1

8 までの数列を求めた理由は、5 までの数列も同じになるから。次にその数列を見て、それぞれの山の大きさに対する Grundy 数を取得する。

	大きさ	Grundy数
山1	5	0
山2	8	1

最後にニム和を求める。「ニム和 0 で負け」を思い出す。したがって 0 ^ 1 = 1 で先手の勝ちである。

解説の模範解答 (AC)

81 ms

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

grundy = []
(0..A.max).each do |i|
  transit = []
  i >= X and transit[grundy[i - X]] = true
  i >= Y and transit[grundy[i - Y]] = true
  case
  when !transit[0]              # 0 がないなら 0
    grundy[i] = 0
  when !transit[1]              # 0 があって 1 がないなら 1
    grundy[i] = 1
  else
    grundy[i] = 2               # 0 と 1 があるなら 2
  end
end

grundy                                      # => [0, 0, 1, 1, 2, 0, 0, 1, 1]

sum = A.inject(0) { |a, e| a ^ grundy[e] }  # => 1
puts sum.zero? ? "Second" : "First"

リファクタリング (AC)

103 ms

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

grundy = []
(0..A.max).each do |i|
  transit = [X, Y].each_with_object([]) do |e, m|
    if i >= e
      previous = grundy[i - e]
      m[previous] = :found
    end
  end
  grundy[i] = transit.index { |e| !e } || transit.size  # => 0, 0, 1, 1, 2, 0, 0, 1, 1
end

sum = A.inject(0) { |a, e| a ^ grundy[e] }              # => 1
puts sum.zero? ? "Second" : "First"