Nim は、2人でおこなうレクリエーション数学ゲーム（組合せゲーム）の一つです。歴史的には、最初に必勝法が数学的に解決したゲームです。双方が最善をつくす場合、どちらが勝つかは最初の個数の組で決まります。
以下のようなゲームを考えます。
有限個のコインの山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。一度に取るコインは1つの山からとし、最低1個は取らなければいけないとする。最後にコインを取ったプレイヤーを勝ちとする。
コインの山の数を N とし、各山のコインの枚数を A1, …, An とした場合、ビットごとの排他的論理和 xor = A1 ^ A2 ^ ,… , ^ An を考えます。これが xor ≠ 0 ならば先手必勝、S = 0 ならば後手必勝です。
なぜそうなるのでしょうか？ コインを取ることで xor ≠ 0 のときは 必ず xor = 0 にすることができます。そして xor = 0 の状態からはどうやっても xor ≠ 0 にしかなりません。コインがなくなったときは xor = 0 なので自分の着手によって xor = 0 の状態を維持することができれば必ず勝つことができます。
Nim の基本問題
石の山が N 個あり、そこには石が A[i] 個あります。先手と後手が交互にひとつの山を選んで 1 個以上の石を取っていき、最初に石を取れなくなったほうが負けです。双方が最善をつくす場合の勝敗を出力してください。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int xor = 0; for (int i = 0; i < N; i++) xor ^= A[i]; if(xor != 0) Console.WriteLine("First"); else Console.WriteLine("Second"); } } |
No.524 コインゲーム
皿は N 枚あり、1 枚目の皿には 1枚のコインが、i 枚目の皿にはコインが i 枚乗っている。
コインは一度に何枚でも取れるが、1回毎に全て同じ皿から取らなければならない。
コインは必ず一枚以上取る。
コインがない状態で自分の番になったら負け。ゲームは終了し、負けなかったほうが勝ちとなる。
先手である自分が勝つかどうか判定せよ。入力されるデータ
N
（ただし 1 ≦ N ≦ 2^32）
N が 2^32 と大きいので xor を計算しようとすると時間が足りません。ただ小さな値で実験をしてみると xor の値は N % 4 == 3 のときだけ 0 になり、それ以外のときは非0となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
using System; public class Program { static void Main() { long N = long.Parse(Console.ReadLine()); // N ≦ 2^32 なのでint型だとオーバーフローする if (N % 4 == 3) Console.WriteLine("X"); else Console.WriteLine("O"); } } |
Nim と Grundy数
最初の例では取ることができる石の数に上限がありませんでした。もし「1 個以上 k 個以下」という条件がついた場合はどうなるのでしょうか？ このようなときに使えるのが Grundy数 です。
Grundy数とはゲームの盤面を非負整数で表したものです。0ならば負け、0以外であれば勝ちです。もし山が 1 つしかなく、自分の番のときに取ることができる石の数が 1 個以上 k 個以下というルールであれば grundy 数は 山にある石の数を k + 1 で割ったときの余りです。山にある残りの石の数を k + 1 で割りきれるように取っていけば必ず勝つことができます。
そしてある盤面のGrundy数はその盤面から遷移できる盤面のGrundy数の集合のMexです。Mexとは集合に含まれない最小の非負整数のことです。集合が空であれば Mex は 0だし、集合が {0, 2, 3} であれば Mex は 1 です。
Nim は盤面の各山のコインの枚数の xor がその盤面のGrundy数になります。よって初期盤面の各山のコインの枚数の xor を計算し、これが 0 以外であれば先手の勝ち、0 であれば後手の勝ちとなります。
No.669 対決!!! 飲み比べ
赳也君は今夜、新宿の『思い出横丁』で酒を飲もうと一軒の焼き鳥屋に入りました。そのお店では次のルールで飲み比べ対決が出来るようです。
・店主と赳也君が交互に酒を飲む
・酒の種類はN種類
・自分のターンにおいて、ある1つの種類の酒を選び、それを1～K(整数値) (ml)飲む
・酒を飲めなくなった方が負け尚、店主も赳也君も非常にお酒に強く「酒を飲めない」⇔「残っているお酒がない」と考えて下さい。
赳也君が先手です。各お酒の量が与えられます。各自最善を尽くすとして、赳也君がこの対決に勝てるかどうかを判定して下さい。
赳也君が勝てるなら「YES」、負けるなら「NO」を出力して下さい。
入力されるデータ
N K
A_1 A_2 … A_N
（ただし、1 ≦ N, K ≦ 1000, 0 ≦ A_i ≦ 1,000,000）
コインが酒に変わっただけです。酒が一種類のときの grundy 数は 残されている量を k + 1 で割ったときの余りであり、複数あるときはそれらの 総xor となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int xor = 0; // grundy 数 for (int i = 0; i < N; i++) xor ^= A[i] % (K + 1); if (xor != 0) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } |
No.153 石の山
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
N 個の石が積まれた山が 1 つある。 A 君と B 君が交互に石を分けるゲームを行う。 分けるときに石を 2 つの山か 3 つの山に分ける。 x を正の整数とするとき、 2x 個の石を x 個と x 個に分ける。 2x + 1 個の石を x 個と x + 1 個に分ける。 3x 個の石を x 個と x 個と x 個に分ける、 3x + 1 個の石を x 個と x 個と x + 1 個に分ける。 3x + 2 個の石を x 個と x + 1 個と x + 1 個に分ける。 以上の操作を選んでできるものとする。 石を最後に分けられなくなったほうが負けである。 例）最初にある石の数が 5 個の場合 まずA君が 2 個と 2 個と 1 個に分ける。 B君は 2 個を 1 個と 1 個に分ける。これで 1 個の山が 3 つと 2 個の山がひとつできる。 A君も 2 個を 1 個と 1 個に分ける。これで 1 個の山が 5 つとなる。 B君はすべての山が 1 個なのでこれ以上分けられない。 B君の負けである。 A君が先手でA君もB君も勝つために最善を尽くすとき、最初の N によって A 君が勝つか B 君が勝つかを判定せよ。 入力されるデータ N （ただし 1 ≦ N ≦ 100） |
分割されることで石の山の数が増えていきますが、考え方は同じです。
ある盤面の Grundy数 はその盤面から遷移できる盤面の Grundy数 の集合の Mex です。そして Mex とは集合に含まれない最小の非負整数のことです。分割前の Grundy数 は分割後の Grundy数 の排他的論理和です。
Grundy数を計算するときに再帰呼び出しをするのでメモ化で処理の高速化を図っています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static int[] memo = { }; // メモ化再帰用 static int GetGrundy(int count) { if(memo[count] != -1) return memo[count]; Dictionary<int, int> dic = new Dictionary<int, int>(); if (count >= 2 && count % 2 == 0) { // 分割前の Grundy数 は分割後の Grundy数 の排他的論理和 int grundy = GetGrundy(count / 2) ^ GetGrundy(count / 2); if(!dic.ContainsKey(grundy)) dic.Add(grundy, 1); } if (count >= 2 && count % 2 == 1) { int grundy = GetGrundy(count / 2) ^ GetGrundy(count / 2 + 1); if (!dic.ContainsKey(grundy)) dic.Add(grundy, 1); } if (count >= 3 && count % 3 == 0) { int grundy = GetGrundy(count / 3) ^ GetGrundy(count / 3) ^ GetGrundy(count / 3); if (!dic.ContainsKey(grundy)) dic.Add(grundy, 1); } if (count >= 3 && count % 3 == 1) { int grundy = GetGrundy(count / 3) ^ GetGrundy(count / 3) ^ GetGrundy(count / 3 + 1); if (!dic.ContainsKey(grundy)) dic.Add(grundy, 1); } if (count >= 3 && count % 3 == 2) { int grundy = GetGrundy(count / 3) ^ GetGrundy(count / 3 + 1) ^ GetGrundy(count / 3 + 1); if (!dic.ContainsKey(grundy)) dic.Add(grundy, 1); } // Mex：集合に含まれない最小の非負整数を探す int ret = 0; while (true) { if(!dic.ContainsKey(ret)) break; ret++; } memo[count] = ret; return ret; } static void Main() { int N = int.Parse(Console.ReadLine()); memo = new int[N + 1]; for (int i = 0; i <= N; i++) memo[i] = -1; if (GetGrundy(N) != 0) Console.WriteLine("A"); else Console.WriteLine("B"); } } |
