HackerRank Game Theory
https://www.hackerrank.com/5-days-of-game-theory
Typical DP Contestというのがありますが、それのゲーム理論版
ゲームの勝敗判定をする問題を解く選択肢
問題
Game of Stones
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones
T個のクエリがある。N個の山があり、そこから2,3,5個のいずれかを取る。
取れなくなったら負け。初手が勝ちならFirst, 後手が勝ちならSecond
Tower Breakers
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers
T個のクエリがある。N個、数Mがある。各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2
A Chessboard Game
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-1-a-chessboard-game
T個のクエリがある。15*15のマスに1つ駒がある。
この駒は、(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond
Nim Game
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-nim-game
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
取り除く石がなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond
Misera Nim
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim
T個のクエリがある。各クエリは、N個の石の個数がS[i]の石の山がある。
順番に石が残っている山から1つ以上の石を取り除く操作をする。
最後に石を取り除いた方が負け。先手が勝ちならFirst, 後手が勝ちならSecond
Nimble Game
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/nimble
T個のクエリがある。0~N-1個の番号がついた箱にC[i]個の石が入っている。
順番に1以上の番号の箱から石を1つ取り出し、それよりも小さい番号の箱に入れる。
操作が行えなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond
Poker Nim
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-poker-nim
T個のクエリがある。N個の石の個数がS[i]の石の山がある。
順番に「石を増やす」か「石を減らす」かする。
ただし「石を増やす」はK回しか行えない。
操作ができなくなった方が負け。先手が勝ちならFirst, 後手が勝ちならSecond
Tower Breakers, Revisited!
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-2
T個のクエリがある。N個の数列があり、各要素はM[i]。
各数をその数の約数のどれかに変換する操作をする。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2
Tower Breakers, Again!!
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-3
T個のクエリがある。N個の数列があり、各要素はM[i]。
ある数Xを選び、それをY個の数Zに分ける(Y*Z = X, Y > 1)。
全ての数が1の状態で番が回ってきたら負け。初手が勝ちなら1, 後手が勝ちなら2
A Chessboard Game, Again!
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game
T個のクエリがある。15*15のマスにk個の駒がある。
この駒は(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動できる。
移動できる駒がなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond
Digits Square Board
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/digits-square-board
T個のクエリがある。N*Nの板にA[y][x]の数が書いてある。
合成数が1つでも書いてある板を選び、縦横どちらかに割る。
割れなくなった方が負け。初手が勝ちならFirst, 後手が勝ちならSecond
Fun Game
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/fun-game
T個のクエリがある。長さNの数列A[i],B[i]がある。
0<= i<Nとあるiを1つ選ぶと、自分はA[i], 相手はB[i]得られる。
各iは1度しか選べない時、初手が勝ちならFirst, 後手が勝ちならSecond, 同点ならTie
Powers Game
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game
T個のクエリがある。*2^1*2^2*2^3*...*2^nというアスタリスクと2の累乗から成る列がある。
順番に*を+か-かに変える処理を行う。
全て変換後の計算結果が17の倍数なら後手Secondの勝ち、そうでないなら先手Firstの勝ち
Deforestation
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation
T個のクエリがある。N頂点の根が1の木がある。
互いに辺を1つ選び、その辺で繋がっている子の部分木を削除する。
部分木を消せなくなったら負け。先手が勝ちならFirst, 後手が勝ちならSecond