🐢
[鉄則B34] Game 7
Grundy 数列を求めたいが、山が大きい場合どうするか問題。
問題を要約する
- 前問と同じ問題
- ただし山が大きい
- X, Y は 2, 3 固定
山が大きいとどうなるのか？
固まる。具体的には、まず Grundy 数列を生成するメソッドを用意する。
def grundy_by(rule:, max:)
grundy = []
max.next.times do |i|
transit = rule.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
end
grundy
end
そして、
- 2 or 3 個ずつ取れる
- 最大の山の大きさは 8
の場合は、
grundy_by(rule: [2, 3], max: 8) # => [0, 0, 1, 1, 2, 0, 0, 1, 1]
とすれば数列が求まる。これを前問に適用すると、
N, X, Y = gets.split.collect(&:to_i) # => [2, 2, 3]
A = gets.split.collect(&:to_i) # => [5, 8]
grundy = grundy_by(rule: [X, Y], max: A.max) # => [0, 0, 1, 1, 2, 0, 0, 1, 1]
sum = A.inject(0) { |a, e| a ^ grundy[e] } # => 1
ans = sum.zero? ? "Second" : "First" # => "First"
puts ans
正しく解ける。ところが、今回の問題では、
- 最大の山の大きさは 1000000000000000000
なので、
grundy_by(rule: [2, 3], max: 1000000000000000000)
として固まってしまう。したがって山が大きいと固まる。
最適化
ためしに数列を 100 まで生成してみると、
grundy_by(rule: [2, 3], max: 100) # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0]
部分的な数列の繰り返しになっているのがなんとなくわかる。5 個ずつ増やしてみると、
grundy_by(rule: [2, 3], max: 4) # => [0, 0, 1, 1, 2]
grundy_by(rule: [2, 3], max: 9) # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2]
grundy_by(rule: [2, 3], max: 14) # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2]
わかりやすい。つまり 4 まで調べれば充分だった。だから、
grundy = grundy_by(rule: [2, 3], max: 4) # => [0, 0, 1, 1, 2]
だけ用意して、たとえば 5 なら、
grundy[5.modulo(grundy.size)] # => 0
丸めれば 0 が出てくる。
解説の模範解答風 (AC)
97 ms
N, X, Y = gets.split.collect(&:to_i) # => [2, 2, 3]
A = gets.split.collect(&:to_i) # => [5, 8]
grundy = [0, 0, 1, 1, 2]
sum = A.inject(0) { |a, e| a ^ grundy[e.modulo(grundy.size)] } # => 1
puts sum.zero? ? "Second" : "First"
2 or 3 個ずつ取れるときの数列が [0, 0, 1, 1, 2] になるのがわかっているためハードコーディングされている。
疑問
この問題は数列のハードコーディングで解けたけど、もし、2 or 3 個の部分が動的に変わる場合どうするんだろう？
Discussion