Game Theory (HackerRank) - okaduki's diary

この記事は解説 Advent Calendar 2017の24日目の記事です。

以下のコンテストの解説です。 www.hackerrank.com

はじめに

競プロ!!Advent Calendarのこの記事 (競プロにおけるNim、Grundy数とNimK - かっさのなにか)に触発されて書きました(というか解いてないことを思い出した)。

以下ではNim, grundy数などの知識を前提としています。全く知識がない、あるいは不安な方は上の記事を読んでから解く and/or 解説を読むことを推奨します。またxorを $\oplus$ で表します。特に記述がなければ、先手(プレイヤー1)と後手(プレイヤー2)が交互に手を打つゲームとし、どちらのプレイヤーが勝つか出力する問題と思ってください。

Game of Stones

概要

Programming Problems and Competitions :: HackerRank

山に石が $N$ 個ある。プレイヤーは山から $2,3,5$ 個いずれかだけ取り除ける。取り除くことができなくなったプレイヤーの負けである。

解法

メモ化再帰。

Tower Breakers

概要

Programming Problems and Competitions :: HackerRank

それぞれに石が $M$ 個ある山が $N$ 山ある。プレイヤーは一つの山に石が $X$ 個あるとき、 $Y$ 個に減らすことができる。ただし $Y$ は $X$ を割り切れなければならない。

解法

$M=1$ のときは明らかに後手勝ち。 $M>1$ とする。 $N$ が偶数ならば後手は先手と全く同じように操作ができるから後手勝ち。 $N$ が奇数ならば先手が最初に $1$ つの山を $1$ にすれば、上と同じ戦略が取れるから先手勝ち。

A Chessboard Game

概要

Programming Problems and Competitions :: HackerRank

$15\times 15$ のチェス盤に石が $1$ つ置いてある。プレイヤーは $(x,y)$ にある石 $1$ つを $(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)$ のいずれかに移動させる。ただし盤面外に移動させることはできない。手を打つことができなったプレイヤーの負けである。

解法

メモ化再帰。

Nim Game

普通のNimなので略。

Misère Nim

概要

Programming Problems and Competitions :: HackerRank

$N$ 山のNimをする。ただし普通のNimと違うところは最後に石を取った人が負け (手が打てなくなったプレイヤーが勝ち) という点である。

解法

まずすべての山が1個の石からなるケースを考える。このときは山の数が偶数なら先手勝ち、奇数なら後手勝ちである。

それ以外のとき、 $S$ を(普通のNimと同じように)すべての山の石の個数の xorをとったものして $S = 0$ のとき、かつそのときに限り、後手勝ちであることを示す。

今、先手番で $S = 0$ とし、先手が手を打つことでこれが $S' \not= 0$ になったとする。

このとき、後手番ですべての山の石が $1$ となることは無いことが分かる。もしそうなったとすると、仮定から先手が選んだ山以外の石の数はすべて $1$ であり、先手が選んだ山はもともと $1$ 個より多くの石があったことが分かる。しかしこのような状況は $S=0$ の下では明らかに起こりえない。

これより、後手番では少なくとも $1$ つの山は $1$ 個より多い石がある。石が $1$ 個より多い山がちょうど $1$ つあるときは、その山を $0$ か $1$ に減らすことで、山の数が奇数となるようにすべての山を $1$ にすることができるので後手が勝つ。そのような山が $1$ つより多くあると、次の先手番ではすべての山が1個の石からなることはない。従って通常のNimと同じようにして $S'' = 0$ となるように後手は手を打つことができ、帰納的に後手勝ちであることがわかる。

逆に先手番で $S \not= 0$ とすると、上の後手番の議論をそのまま適用できるので先手勝ちである。

よってすべての山が $1$ 個の石である場合を例外扱いすることで、普通のNimと同じように解ける。

解説だと全部 $1$ のときだけ場合分けすればいいとしか書いてないし、それが正しそうな理由もよく分からなかった。自分は実験してなんとなく規則性を見つけて適当に投げた。実験せずに気付けるかと言われると微妙。

Nimble Game

概要

Programming Problems and Competitions :: HackerRank

$N$ 個の箱が一列に並んでいて、 $0,1,2,\dots$ と番号が付いている。各箱には石が $c_i$ 個入っており、プレイヤーは $i$ 番目の箱にある石 $1$ つを箱 $j \lt i$ に移すことができる。先に手を打つことができなくなったプレイヤーの負けである。

解法

位置 $i$ にある石はそれより小さい $j \lt i$ のどこへでも動かせる。これはNimの $1$ つの山にある石の個数が $i$ 個であるときの状況とちょうど対応している。よって $S = \displaystyle\bigoplus_{c_i \bmod 2 = 1}{i}$ が $0$ なら後手勝ちである。

Poker Nim

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $c_i$ 個石がある。プレイヤーは各ターンで $1$ つの山から $1$ 個以上の石を取り除くか、あるいは追加することができる。ただし、石を追加できる回数は各プレイヤー、各山に対して高々 $K$ 回までである(個数は任意)。最後の石を取り除いたほうが勝ちである。

解法

石を追加しないNimと全く同じ結果になる。つまり、 $S = \bigoplus_i c_i = 0$ のとき、かつそのときに限り、後手必勝となる。 $S=0$ のときは先手が石を取り除こうが追加しようが、後手は先手と同じことをすればNim和は $0$ になる。また石の追加は高々 $K$ 回までしかできず、必ず有限回で終わるので後手必勝。

$S \not= 0$ のときは適当に石を取り除いて $S = 0$ の状態に持っていけるので先手必勝である。

Tower Breakers, Revisited!

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $h_i$ 個石がある。プレイヤーは $1$ つの山にある $X$ 個の石を $Y \lt X$ まで減らすことができる。ただし $Y \geq 1$ は $X$ の約数でなければならない。最後の石を取り除いたほうが勝ちである。

解法

山が $1$ つで $x$ 個石があるとする。このときのgrundy数がどうなるか考える。 $x$ のある約数 $d$ のgrundy数を $g_d$ とすると、 $d$ の任意の約数 $d'$ にも $x$ から遷移できるので、 $x$ のgrundy数 $g_x$ は少なくとも $g_d + 1$ 以上である。これを $x$ のすべての約数にわたって考えれば $g_x = \displaystyle \max_{d \nmid x}{(g_d+1)}$ となる。

よくよく考えるとこれは $x$ の重複を含めた素因数の個数(例えば $x = 2^2\times3^1$ なら $2+1=3$ )と一致することがわかる (素因数 $p$ で $x$ を割ったものならどれでも最大になるため) ので、各 $h_i$ のこれを調べて最後にそれらのNim和をとればよい。

Tower Breakers, Again!

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $h_i$ 個石がある。プレイヤーは $1$ つの山にある $X$ 個の石を、 $Z$ 個の石からなる $Y$ 個の山に分けることができる。ただし $Y > 1, Y \times Z = X$ でなければならない。最後の石を取り除いたほうが勝ちである。

解法

基本的に $1$ つ前の問題と同じで重複を含めた素因数の個数がgrundy数となる。ただし $2$ を素因数にもつときは一度だけしか数えない( $2^i$ のグランディ数が $1$ となるから)。

Chessboard Game, Again!

概要

Programming Problems and Competitions :: HackerRank

$15\times 15$ のチェス盤にいくつか石が置いてある。 $1$ つのマスに石が複数置いてあっても良い。プレイヤーは $(x,y)$ にある石 $1$ つを $(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)$ のいずれかに移動させる。ただし盤面外に移動させることはできない。手を打つことができなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。盤面が $15 \times 15$ で、ありうる遷移が高々 $4$ なので愚直に計算しても十分に間に合う。位置 $(x,y)$ から動かせる手 $(x',y')$ について $x+y > x'+y'$ が成り立つから、 $x+y$ が小さいものから順に計算することができる。

Digits Square Board

概要

Programming Problems and Competitions :: HackerRank

$N \times N$ のマスに整数 $x (1 \leq x \leq 9)$ が書かれている。プレイヤーは盤面の面積が $1$ より大きく、かつ素数でないような数字が少なくとも $1$ つ書かれているとき、盤面を水平方向か垂直方向に $2$ つに分割することができる。手を打つことができなくなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。 $dp(x_1,y_1,x_2,y_2) = \text{｢元の盤面の部分長方形で左上が}(x_1,y_1)\text{で右下が}(x_2,y_2)\text{のgrundy数｣}$ でメモ化再帰する。素数でないものが部分長方形に入っているかを累積和で前計算しておけば、盤面が分割できるかどうかは $\mathcal{O}(1)$ で判定できる。上の状態が $\mathcal{O}(N^4)$ あり、各状態からの分割方法は $\mathcal{O}(N)$ あるので、全体で $\mathcal{O}(N^5)$ で計算できる。

Fun Game

概要

Programming Problems and Competitions :: HackerRank

長さ $N$ の $2$ つの数列 $A=(a_1,\dots), B=(b_1,\dots)$ がある。プレイヤー $1$ は $A$ から、プレイヤー $2$ は $B$ から交互に数字を選んでいく。ただし $a_i$ がすでに選ばれていたら $b_i$ を選ぶことができず逆も同様。なのでちょうど $N$ 回の操作でゲームは終わる。

各プレイヤーが選んだ数の総和を計算し、大きい方が勝ち、同じなら引き分けである。

解法

この手の $2$ つの数列から片方を選ぶみたいな問題は適当な評価値を決めて、大きい方から選んだりdpしたりすることが多い気がするのでそうする。

このゲームは次のようなゲームに置き換えられる。

プレイヤー $1$ は初期点として $\sum_i{a_i}$ を持っている。
数列 $C = (a_1+b_1, \dots)$ がある。
プレイヤー $1$ は $C$ から数字を一つ消すことができ、プレイヤー $2$ は選んだ数だけプレイヤー $1$ の点数を減らせる。
最後にプレイヤー $1$ の点数が正ならばプレイヤー $1$ の勝ち、 $0$ なら引き分け、負ならプレイヤー $2$ の勝ち。

なので $C$ を計算、ソートして、数字が大きいものから順番に消す、点数を減らすことを交互にすればよい。

Powers Game

概要

Programming Problems and Competitions :: HackerRank

文字列 $\heartsuit 2^1 \heartsuit 2^2 \heartsuit \dots \heartsuit 2^n$ がある。プレイヤーは交互に $\heartsuit$ を $+$ か $-$ のどちらかに $1$ つずつ書き換える。最後にすべての $\heartsuit$ が無くなったら数式を計算し、 $17$ で割りきれたら後手勝ち、そうでなければ先手勝ち。

解法

$x_i = 2^i \bmod 17$ だけを気にすればいいから、現れる数字は実質 $0 \leq x_i \lt 17$ だけとみなせる。また、 $x_i = x_j (i \not= j)$ なるものがあれば、お互いに打ち消すように手を指すことができる (片方が $+$ に書き換えたらもう片方は $-$ に変える)ので、奇数個あるものだけ着目すれば良い。

あとは $dp(i,r,B) = \text{｢プレイヤー}i\text{が今までの和が}r\text{であり、残り使える集合が}B\text{から始めるときに勝てるか｣}$ のように $B$ をbitとして使いメモ化再帰で解ける。 $n \leq 10^6$ なので $n=1$ から順番に前計算しておけば良い。

Deforestation

Programming Problems and Competitions :: HackerRank

既出。同じ問題がhttps://beta.atcoder.jp/contests/agc017/tasks/agc017_dにある。ハッケンブッシュ(Hackenbush)というゲームがあってそれの特殊な形である。

Tower Breakers - The Final Battle

概要

Programming Problems and Competitions :: HackerRank

$N$ 個の石がある。 $N=1$ となるまでプレイヤーは以下の操作を交互にする。

プレイヤー $1$ は $N = n_1 + n_2 + \dots + n_k,\; k \geq 2$ となるように自由に石を分割する。
プレイヤー $2$ はこの中から $i$ 番目の山を選び、 $N = x_i$ としてゲームを続ける。このときコイン $i^2$ 枚を得る。

プレイヤー $1$ はプレイヤー $2$ が得られるコインの枚数を最小化、プレイヤー $2$ は最大化しようとする。このとき最終的に得られるコインの枚数はいくらか。

解法

小さいケースで実験すると $N$ がある程度大きくなっても答えは大きくならないと予想ができる。

そこで $f(m) = \text{｢答えがmとなるような最大のN｣}$ とする。明らかに $f$ は単調増加になるから、 $f(m) \leq N$ となるような最大の $m$ が求める答えである。 $i$ 番目の山を選ぶとコインを $i^2$ 払うことになるから、 $f(m) = \displaystyle\sum_{m-i^2\geq 0}{f(m-i^2)}$ となる。 $m=121$ で $f(m) \gt 10^{18}$ となるから愚直に計算しても実行時間は十分間に合う。