🐢

[鉄則A33] Game 2 (ニム和)

2024/05/28に公開

Ruby

解法が美しいニム和の基本問題。

問題を要約する

N 個の山がある
どれかの山から1個以上の石をとる
取れなくなった方の負け

それぞれの山の石の数は入力時に決まる。

前提知識: ニム和とは？

すべての XOR を取った結果のこと

前提知識: 負ける条件

同じ個数の局面を迎えた側が負ける

	先	後	先
1	1		×
1		1	×

たとえば二つの山が 1, 1 の状態から始めた場合、真似をされた先手が空の局面を迎えて負ける。100, 100 でもそれは同じ。ここで開始局面のニム和を調べると 1 ^ 1 = 0 になる。つまり、

ニム和 0 で負け

となる。これだけでいいので覚えておく。

判定法

ニム和を 0 から 0 にできない → 負けから負けにできない
ニム和を !0^[1] から 0 にできる → 勝ちから負けにできる

混乱してきたら「から」のあとに「次の局面を相手の立場で」を補完する。

負けから負けにできないパターン

	先	後	先
1	1		×
1		1	×

1, 1 で開始局面を迎えて負けだと感じた先手は、なにをやろうにも次の局面を相手の立場で負けの局面にできない。つまり先手は負ける。これをひとことで言えば、

ニム和が 1 ^ 1 = 0 の局面を迎えたから先手は負ける

勝ちから負けにできるパターン

	先	後	先	後
1		1		×
2	1		1	×

1, 2 を 1, 1 の状態にし「同じ個数の局面」を後手に迎えさせることで後手を負けにできる。つまり先手が勝つ。これもひとことで言えば、

ニム和が 1 ^ 2 = 3 の局面を迎えたから先手が勝つ

同じ個数の局面を迎えたのに先手が勝つパターン

	先	後	先	後
1	1			×
1		1		×
1			1	×

「同じ個数の局面を迎えた方が負ける」というのであれば 1, 1, 1 で先手が負けるはずなのに後手が負けているのはどうしてだろうか？これは、山が二つの場合にたまたま辻褄が合っていたというだけで、三つ以上の山があった場合には当てはまらない。そこで、これもニム和で考えると、

ニム和が 1 ^ 1 ^ 1 = 1 の局面を迎えたから先手が勝つ

となって不思議なことに辻褄が合う。

まとめ

「同じ個数の局面を迎えた方が負ける」は山が二つの場合にのみ正しい
- それは x ^ x = 0 でニム和が 0 になっているから
ニム和を !0 で迎えた方が勝つ
- ニム和を 0 で渡すことができるから
  (特定の山の値を減らして XOR の結果が 0 になるように微調整できる余地があるから)

解説の模範解答 (AC)

67 ms

N = gets.to_i                         # => 2
A = gets.split.collect(&:to_i)        # => [7, 7]
sum = A.reduce(:^)                    # => 0
ans = sum.zero? ? "Second" : "First"  # => "Second"
puts ans

参考

脚注

0 ではないという意味 ↩︎