hackerrankのGame Theoryを解いたまとめ
ゲーム系問題があつまっている。
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges
grundy数とかNimとかの勉強によかった。
Game of Stones
2人のプレイヤーがいて各ターンで2,3,5個の石を取り除く行動ができる。行動できなくなったら負け。
遷移先の状態に負けの状態があれば勝ち、全部勝ちなら負けと実装すれば通る。制約的に愚直に実装すれば大丈夫。
Tower Breakers
N個の高さMのタワーがある。二人のプレイヤーはタワーを1個選んで高さXのタワーをX未満のXの約数Yの高さのタワーに変更することができる。行動できなくなったら負け。
高さはすべて等しいため全てのタワーのgrundy数は等しい。よってタワーの数が偶数ならXORを取った結果は0になり、player2の勝ちとなる。また、タワーの高さが1ならplayer1はその時点で行動できないためplayer2の勝ち。
A Chessboard Game
15*15のチェス盤とチェス盤の上にコマが一つある。2人のプレイヤーは順番にこのコマを規則に沿って動かす。動かせなくなったら負け。
Game of Stonesと同様に愚直に実装すれば通る。
Nim Game
よくあるNim
XORをとる
Misere Nim
最後の石を取ったら負けのNim
Nimと同様にXORが0となる状態で相手に渡すのが基本でXORが0のとき負け。山の石の数が1以下のときは山の個数が奇数のとき、つまりXORが1のとき負け。
Nimble Game
squqreがN個あり、squareにはC[i]個のコインが存在している。プレイヤーはsquare-iからsquare-j(j < i)にコインを1枚移すことができる。動かせなくなったら負け。
i番目のsquareにコインが存在するのは、Nimのi枚の石の山に置き換えることができる。コインが偶数枚であればxorは0なので奇数枚のコインがあるsquareのindexのXORを取った結果で判断できる。
Poker Nim
N個の山がある。プレイヤーはいずれか一つの山から「一枚以上消す」「一枚以上加える」のいずれかを行う。加える行動はk回までしか行えない。行動できなかったら負け。
XORが0の状態で加える動作を行ったとしてもXORが0の状態を相手に押し付けることは可能。普通のNimと同様に判定できる。
Tower Breakers, Revisited!
N個のタワーがあり、各タワーの高さはh[i]である。各プレイヤーはどれかタワーを一つ選び高さをその約数の高さに変更することが出来る。行動できなかったら負け。
各塔のgrundy数はそのタワーの高さの素因数の個数になる。
Tower Breakers, Again!
N個のタワーがあり、各タワーの高さはh[i]である。各プレイヤーは高さXのタワーを高さYのタワーZ個に変えることができる。(Y>1, X=Y*Z) 行動できなかったら負け。
n個の独立した状態s[1],s[2],…,s[n]のgrundy数はs[1],s[2],…,s[n]それぞれのgrundy数のXORに一致するという定理を使う。高さ1のタワーをgrundy数0として設定し、grundy数の定義にしたがって計算していく。
Chessboard Game, Again!
15×15の大きさのチェスボードの上にコインがk枚存在する。各プレイヤーはコインを一つ選択し規則にしたがって移動させる。移動させられなかったら負け。
チェスボード上の各マスにgrundy数を割り当てる。もうコインを動かすことができないマスに0を割り当てあとは定義に従って計算する。
Digits Square Board
N×Nマスのボードが与えられる。各マスには1から9の数字がかかれている。各プレイヤーは合成数が一つ以上かかれているボードを選び、垂直・水平に二分割する。行動できなくなったら負け。
各ボードにgrundy数を割り当てる。合成数のみが含まれているかどうかを判定するのに累積和をしないとTLEするので注意。
Powers Game
n要素の数列A、Bが与えられる。手番にi(1<=i<=n)を選択することでプレイヤー1はa[i]、プレイヤー2はb[i]を得られる。最終的な点数の合計が高いほうが勝ち。
a[i]+b[i]が高い方から順に取る。
Powers Game
2^1,2^2,…,2^nの数列の要素を一つ選んでプラスかマイナスをつける。最終的な総和が17の倍数になればplayer2の勝ち。それ以外ならplayer1の勝ち。
2^n, -2^n (mod 17) を計算すると周期8で周期性、対称性がある。nが8の倍数のとき、player1が選んだものに合わせて0 (mod17)となるように取ることで17の倍数にすることができplayer2の勝ちとなる。
Deforestation
根が1、頂点数がNの木が与えられる。各プレイヤーは任意の辺を取り除くことができ、根とつながっていない頂点は取り除かれる。操作できなくなったら負け。
子の部分木のパスの長さが石の数の山のNimに帰着できる。（それぞれの子の部分木の長さを任意の長さに短く出来るためNimの操作と同じ）子の部分木のパスの長さのXORを取ったものを各頂点のgrundy数とすると、根のgrundy数が0ならBob、0以外ならAliceの勝ちになる。
Tower Breakers - The Final Battle
player1は高さHの塔をx個の塔に分割する。(塔iの高さをh[i]とすると H = \sum_{i=0}^{x} h[i] となるように高さを決める) player2はx個のうちk番目(1<=k<=x)の塔を選択する。player2はk^2円を獲得し、player1はH=h[k]として再び手番を行う。playerが最適な行動をしたときplayer2はいくら獲得するか。
(解説を読んだけどDPの遷移がよく理解できていない…)
まず、得られる金額の上界は4*logNになる。player1が高さHの塔を二分割し、player2が2番目の塔を選び4円を獲得するとする。この方法ではlogN回で終了するため、4*logNが上界となる。
dp[x] = (答えがx以下になる最大の塔の高さ) としたDPを考える。4*log_{2}10^18 ≒ 239.1 より、配列の要素数は300程度で問題ない。
DP遷移は dp[x] = \sum_{j=1}^{sqrt(x)} dp[x-j^2] となるのでこれを前計算しておく。与えられたNについて二分探索しインデックスの値が答えとなる。dpの値はlong long intの値も超えるので注意。
