🐢
[鉄則B33] Game 6 (ニム和)
解法が美しいニム和の応用問題。
問題を要約する
- 二次元グリッド上にいくつかの駒がある
- 上または左に1マス以上動かせる
- 動かせなくなった方の負け
問題を理解する
駒が一つで (1, 1) にあったとする。
| 0 | 1 | |
|---|---|---|
| 0 | ||
| 1 | ○ |
先手は駒を左か上に動かせる。仮に上に動かしたとする。
| 0 | 1 | |
|---|---|---|
| 0 | ○ | |
| 1 |
続いて後手は左に一つ動かす。
| 0 | 1 | |
|---|---|---|
| 0 | ○ | |
| 1 |
先手はもう動かせないので負ける。
考え方
次の (1, 1) だと先手が負けるのがわかった。
| 0 | 1 | |
|---|---|---|
| 0 | ||
| 1 | ○ |
次の (1, 2) だとどうだろう？
| 0 | 1 | |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ○ |
上に一つだけ動かした場合に (1, 1) の状態になり後手が負ける。まとめると、
- (1, 1) → 負け
- (1, 2) → 勝ち
思い出してみると、これは前問の山の石の数と同じ法則である。
- 負け
| 先 | 後 | 先 | |
|---|---|---|---|
| 1 | 1 | × | |
| 1 | 1 | × |
- 勝ち
| 先 | 後 | 先 | 後 | |
|---|---|---|---|---|
| 1 | 1 | × | ||
| 2 | 1 | 1 | × |
したがって考え方は、
- 座標の x, y 成分同士のニム和が 0 なら負け
となる。
駒が複数ある件は？
駒と駒は干渉しない (同じマスにおける) ため、たとえば、
- 駒1 → (1, 1)
- 駒2 → (2, 2)
だったとしても、
- 山1 → 石1個
- 山2 → 石1個
- 山3 → 石2個
- 山4 → 石2個
と考えることができ、その場合のニム和は 1 ^ 1 ^ 2 ^ 2 なので、この問題の最終的な解法は、
- すべての座標の x, y 成分をフラットにしてそのニム和が 0 なら負け
となる。
実装 (AC)
182 ms
N, H, W = gets.split.collect(&:to_i) # => [1, 3, 5]
AB = N.times.collect { gets.split.collect(&:to_i).collect(&:pred) } # => [[1, 3]]
sum = AB.flatten.reduce(:^) # => 2
puts sum.zero? ? "Second" : "First"
Discussion