今回は石取りゲームの必勝法を考えます。
K – Stones
N 個の正整数からなる集合 A = { a_1, a_2, …, a_N } があります。
最初に、K 個の石からなる山を用意します。二人は次の操作を交互に行います。
A のなかからひとつ選び、山からちょうど同じ個数の石を取り去る。
先に操作を行えなくなった人が負け。二人が最適に行動する場合どちらが勝つかを判定し、先手が勝つなら “First”、後手が勝つなら “Second” を出力してください。
入力されるデータ
N K
a_1 a_2 … a_N
（ただし 1 ≦ N ≦ 100, 1 ≦ K ≦ 10^5
1 ≦ a_1 ＜ a_2 ＜ … ＜ a_N ≦ K ）
石が x 個ある状態で自分に順番が回ってきたときの勝敗を Win（x）とすると、x == 0 の場合は負け、それ以外の場合は再帰呼び出しで Win（x – i）を考えます。i は取ることができる石の数すべてを考えます。i を変えて Win（x – i）の結果を調べてひとつでも勝てる方法があるならそれを選択して勝ちます。ない場合は負けとなります。
ただし Win を呼び出すときには残りの石の数だけでなくどちらの手番なのかという情報も渡す必要があります。そこで Win(int n, bool isFirst)（第一引数：残りの石の数、第二引数：手番は先手かどうか？、戻り値：手番があるほうが勝つか？）を定義することを考えます。
また再帰呼び出しをするときは同じ引数で何度も呼び出される場合があるので、戻り値を返すときにこれを配列のなかに保存し、同じ引数で再度呼び出されたときは処理はしないで保存されている値を返すことで高速化を図ります（メモ化再帰）。
|
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 |
public class Program { static bool[,] memo = new bool[1, 1]; // 返した値を記憶しておく static bool[,] ismemo = new bool[1, 1]; // Win(int n, bool isFirst)の値はすでに計算したか？ static int[] A; // 問題で与えられた 集合 A static bool Win(int n, bool isFirst) { int player = isFirst ? 0 : 1; // 先手：0、後手：1 if (ismemo[player, n]) return memo[player, n]; // すでに計算されているのであればそれを返す if (n == 0) return false; // 残り 0 個で手番が回ってきたら負け bool b = false; foreach (int v in A) { // 相手を負けにする状態で手番を渡す方法があるか探す。 // ひとつでもあれば自分の勝ちなので true を返す if (n - v >= 0 && !Win(n - v, !isFirst)) { b = true; break; } } // 結果を返す前にメモする。そのあと結果を返す ismemo[player, n] = true; memo[player, n] = b; return memo[player, n]; } } |
あとは入力を受け取ってWinを呼び出せば結果を出力することができます。
|
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 |
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]; } A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); memo = new bool[2, K + 1]; ismemo = new bool[2, K + 1]; if (Win(K, true)) Console.WriteLine("First"); else Console.WriteLine("Second"); } } |
G – 石取りゲーム
同じ石取りゲームですが、石を取るルールが違います。
N 個の石からなる山を用意します。一番最初に先手が石をとるときは 1 個以上 P 個以下の好きな個数だけ石をとれます。それ以降については、各プレーヤーは 1 個以上、直前にとられた石の個数 + 1 個以下の好きな個数だけ石をとれます（例：前の人が石を 3 個取った場合、次の人は 1 個以上 4 個以下の石を取ることができる）。
N と P が与えられるので双方が最善をつくした場合、先手が勝つ場合は first、後手が勝つ場合は second と 出力してください。
入力されるデータ
N
P
（ただし 1 ≦ N ≦ 500, 1 ≦ P ≦ N ）
今度は前の人の行動で次の人が取れる石の数が変化するので、残りの石数、どちらに手番があるのかだけでなく、次の人が取ることができる石の最大数も渡さなければなりません。またメモ化するときの配列も2次元配列ではなく3次元配列にしなければなりません。N と P の上限からこれでも問題なく動作してくれそうです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static bool[,,] memo = new bool[1, 1, 1]; static bool[,,] ismemo = new bool[1, 1, 1]; static bool Win(int n, bool isFirst, int count) { int player = isFirst ? 0 : 1; if (ismemo[player, n, count]) return memo[player, n, count]; if (n == 0) return false; bool b = false; for (int i = 1; i <= count; i++) { if (n - i >= 0) { // i 個取ったら次の人は i + 1 個取ることができる bool ret = Win(n - i, !isFirst, i + 1); if (ret == false) { b = true; break; } } } ismemo[player, n, count] = true; memo[player, n, count] = b; return memo[player, n, count]; } static void Main() { int N = int.Parse(Console.ReadLine()); int P = int.Parse(Console.ReadLine()); memo = new bool[2, N + 1, N + 2]; ismemo = new bool[2, N + 1, N + 2]; if (Win(N, true, P)) Console.WriteLine("first"); else Console.WriteLine("second"); } } |
D – Stones
数列 (A_1, …, A_K) を使って、高橋君と青木君が石取りゲームをします。
最初、山には N 個の石があります。高橋君から順に、二人が交互に次の操作を行います。
現在山にある石の個数以下であるような A i を 1 つ選ぶ。山から A i 個の石を取り除く。
山から石がなくなったとき、ゲームは終了します。二人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、高橋君は何個の石を取り除くことができますか？
入力されるデータ
N K
A_1 A_2 … A_K
（ただし、1 ≦ N ≦ 10^4, 1 ≦ K ≦ 100
1 ＝ a_1 ＜ a_2 ＜ … ＜ a_K ≦ N ）
これ、「各手番で石を取れるだけ取る」でよいのではないか？と思うかもしれませんが、実は違います。
全部で石は 10 個あり、A = {1, 3, 4} だとします。この場合「各手番で石を取れるだけ取る」だと先手は 4 個取ることになりますが、後手も 4 個取ると次は 1 個しか取れません。だから答えは 5 個でよいのでしょうか？
先手は最初に 3 個だけ取った場合、後手がどのように行動しても次に必ず 3 個取ることができます。N = 10, A = {1, 3, 4} のときの解は 5 ではなく 6 なのです。
ということでこの問題は動的計画法で解きます。
dp[n] を 石が n 個残っている状態からゲームを始めたとき、先手が取ることのできる石の個数と定義します。
先手番が A_i 個の石を取ったとき、最終的に取れる石の個数は、A_i + 「石が n – A_i 個 残っている状態からゲームを始めたとき、後手が取ることのできる石の個数」なので、すべての i についてこれを調べて最大になる値が dp[n] に代入すべき値です。
|
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 |
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[] dp = new int[N + 1]; for (int n = 0; n <= N; n++) { int max = 0; foreach (int v in A) { if (n - v < 0) continue; int ret = n - dp[n - v]; max = Math.Max(max, ret); } dp[n] = max; } Console.WriteLine(dp[N]); } } |
B – 石取り大作戦
高橋君と青木君は N 個の石からなる石の山を使って石取りゲームをすることにしました。ゲームのルールは以下の通りです。
プレイヤーは交互に 1 個以上の石を山から取る。
最後の石を取ったプレイヤーの勝利である。
先手の高橋君は一度に最大 A 個までの石を取ることが可能であり、後手の青木君は一度に最大 B 個までの石を取ることが可能である。両者が最適に行動したとき勝利するのはどちらでしょうか？ 先手の高橋君が勝つ場合は Takahashi を、後手の青木君が勝つ場合は Aoki を 出力してください。
入力されるデータ
N
A B
（ただし、1 ≦ N, A, B ≦ 10^9）
この問題は N, A, B が巨大な数なので実際に配列を生成することができません。そこでうまく計算することで解を求めなければなりません。
N ≦ A の場合は先手が最初にすべての石を取ってしまうことができるので先手必勝です。
では N ＞ A の場合はどうでしょうか？ A = B の場合から考えます。
N = A + 1 の場合は先手がどのように石を取っても、2手目に後手は残りの石をすべて取ることができるので後手が必ず勝ちます。また N が A + 1 で割り切れる場合も後手は A + 1 で割り切れるように石を残すことで、最後は N = A + 1 と同じ状態に持ち込めるので必ず勝つことができます。
N が A + 1 で割り切れない場合は初手で先手が A + 1 で割り切れるように石を残すことで、後手に負けパターンを押し付けることができるので先手が必ず勝ちます。
N ＞ A かつ A ＞ B の場合は先手は残りの石が B より多くなるように取ることで、再度自分に手番が回ってきたときに A が残りの石と同じかそれより大きくなっている状態に持ち込めるので先手が必ず勝ちます。また N ＞ A かつ A ＜ B の場合は似たような論法で後手が必ず勝つことになります。
まとめると
◇ N ≦ A の場合 先手必勝
◇ N ＞ A の場合
◇ ◇ A = B で N が A + 1 で割り切れる場合は後手必勝、そうでないなら先手必勝
◇ ◇ A ＞ B なら先手必勝
◇ ◇ A ＞ B なら後手必勝
|
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 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int A, B; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); A = vs[0]; B = vs[1]; } if (N <= A) Console.WriteLine("Takahashi"); else { if (A == B) { if(N % (A + 1) == 0) Console.WriteLine("Aoki"); else Console.WriteLine("Takahashi"); } if (A > B) Console.WriteLine("Takahashi"); if (A < B) Console.WriteLine("Aoki"); } } } |
