E - カード取りゲーム / Card Taking Game Editorial
by 
MMNMM
この問題は、組合せゲーム理論における不偏ゲームを題材とした問題です。 不偏ゲームとは、どのような盤面においても \(2\) 人のプレイヤーがとれる選択が等しいゲームのことをいいます。 不偏ゲームの解析には、Sprague–Grundy の定理を用いるのが便利です。
ニムとその和
まず、次のようなゲームを考えます。
ニム (Nim)
テーブルの上に石の山が \(1\) つあり、その山には石が \(K\) 個含まれている。 プレイヤーはそれぞれの手番で山から \(1\) つ以上の石を取り除く。 石を取り除けなくなった（山に石がひとつもなくなった状態で手番が回ってきた）プレイヤーが負け。
このゲームは \(K\gt0\) なら先手必勝、\(K=0\) なら後手必勝です。
また、不偏ゲームの和を次のように（再帰的に）定義します。
\(2\) つの不偏ゲーム \(G,H\) の和 \(G+H\) を、\(G\) から \(1\) 手進めた状態としてありえるゲームの集合を \(\lbrace G _ 1,G _ 2,\ldots\rbrace\) 、\(H\) から \(1\) 手進めた状態としてありえるゲームの集合を \(\lbrace H _ 1,H _ 2,\ldots\rbrace\) としたとき、\(1\) 手進めた状態としてありえるゲームの集合が \[\lbrace G _ 1+H,G _ 2+H,\ldots\rbrace\cup\lbrace G+H _ 1,G+H _ 2,\ldots\rbrace\] であるようなゲームとして定める。
これは結合法則を満たすことが確かめられるので、\(3\) つ以上のゲーム \(G _ 1,G _ 2,\ldots,G _ k\) の和を \(G _ 1+G _ 2+\cdots+G _ k\) と書くことにします。
簡単に言うと、ゲームの和は「どれか \(1\) つのゲームを選んで \(1\) 手進める」ことができるゲームです。 （今回のゲームも、\(A _ 1\) 枚のカードからなる山 \(1\) つだけのゲーム \(,A _ 2\) 枚のカードからなる山 \(1\) つだけのゲーム \(,\ldots,A _ N\) 枚のカードからなる山 \(1\) つだけのゲーム の和と考えることができます。）
次に、不偏ゲームが等価であることを次のように定義します。
\(2\) つの不偏ゲーム \(G _ 1,G _ 2\) が等価であることを、任意の不偏ゲーム \(H\) に対して \(G _ 1+H\) の勝敗（先手必勝か後手必勝か）と \(G _ 2+H\) の勝敗が等しいこととして定める。\(G _ 1,G _ 2\) が等価であることを、\(G _ 1=G _ 2\) と書く。
石が \(K\) 個のニムを、簡単のため \(*K\) と書くことにします。
ニムの和について、次の事実が知られています。
\(*x+*y=\ast(x\oplus y)\) （ここで、\(\oplus\) はビットごとの排他的論理和）
Sprague–Grundy の定理
Sprague–Grundy の定理とは、以下のような定理です。
Sprague–Grundy の定理
任意の不偏ゲーム \(G\) について、ある非負整数 \(K\) が存在し、\(G\) は \(*K\) と等価である。 このような \(K\) を \(G\) の Grundy 数と呼び、\(\mathcal G(G)\) と書く。
競技プログラミングにおける不偏ゲームの解析では、これを使って与えられた盤面と等価なニムを求めることが多いです。
Grundy 数を具体的に求めるには、次の事実を利用することが多いです。
不偏ゲーム \(G\) について、\(G\) から \(1\) 手進めた状態としてありえるゲームの集合を \(\lbrace G _ 1,G _ 2,\ldots\rbrace\) としたとき、次の等式が成り立つ。\[\mathcal G(G)=\operatorname{mex}\lbrace\mathcal G(G _ 1),\mathcal G(G _ 2),\ldots\rbrace\] ただし、整数の集合 \(S\) に対する \(\operatorname{mex} S\) は \(S\) に含まれない最小の非負整数を表す。
今回の問題では、\(N=1\) のゲームに対する Grundy 数を決定したあと、ビットごとの排他的論理和をとることで答えを求めることができます。
\(N=1\) のとき、Grundy 数は \(A _ 1\) を \(K+1\) で割った余りになることが示せます。 よって、\(A _ 1\) を \(K+1\) で割った余り \(,A _ 2\) を \(K+1\) で割った余り \(,\ldots,A _ N\) を \(K+1\) で割った余り の総 xor が \(0\) ならば青木君が、そうでなければ高橋君が勝つことがわかります。
実装例は以下のようになります。
#include <iostream>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
int grundy_number = 0;
for (int i = 0; i < N; ++i) {
int A;
cin >> A;
// 1 つの山の Grundy 数は A % (K + 1)
// xor が全体の Grundy 数になる
grundy_number ^= A % (K + 1);
}
// Grundy 数が 0 なら青木君が、そうでなければ高橋君が勝つ
cout << (grundy_number ? "Takahashi" : "Aoki") << endl;
return 0;
}
N, K = map(int, input().split())
grundy_number = 0
for A in map(int, input().split()):
# 1 つの山の Grundy 数は A % (K + 1)
# xor が全体の Grundy 数になる
grundy_number ^= A % (K + 1)
# Grundy 数が 0 なら青木君が、そうでなければ高橋君が勝つ
print('Takahashi' if grundy_number > 0 else 'Aoki')
posted:
last update: