競プロのゲーム系の問題

競プロ

ゲーム系の問題まとめ

探索系

概要

ある状態が勝ちか負けかをシミュレーションする

問題

  • HackerRank - Game of Stones
    • n個の石がある。プレイヤーは2個か3個か5個の石を交互に取り除いていく。動かせなくなった方が負け。先手と後手どちらが勝つか求めよ。
  • HackerRank - A Chessboard Game
    • 15×15のチェス盤があり、コインが座標(x, y)におかれる。プレイヤーは交互にコインを(x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2)に移動していく。動かせなくなった方が負け。先手と後手どちらが勝つか求めよ。
  • HackerRank - Permutation game
    • 1からNまでの数字の順列がある。プレイヤーは交互に数値をひとつ取り除いていく。残った数値を昇順になるようにした方が勝ち。先手と後手どちらが勝つか求めよ。
  • ARC038 - B マス目と駒
    • H×Wのマス目がる。駒を(1, 1)に置く。各プレイヤーは駒をひとつ下かひとつ右下かひとつ右のマスのうち障害物のないマスに動かす。動かせなくなった方が負け。先手と後手どちらが勝つか求めよ。

Nim系

概要

Nimゲームは石の個数をすべての山についてxorをとったとき0なら負け、0以外なら勝ちとなる。
xorが0だとすると，ひとつの山しか操作できないため、ここから石を1つ以上とると必ずxorは0でなくなる。xorが0以外だとすると，石の数が最大の山を操作することで必ずxorを0にすることができる。
このことから、xorが0の負け状態からは、相手に0以外の勝ち状態しか渡すことができず、またxorが0以外の勝ち状態からは必ず相手にxorが0の負け状態を渡すことができる。
Nimそのままの問題がでることはなく、うまく解釈してNim問題に帰着できるような問題がでる。

問題

  • HackerRank - Introduction to Nim Game
    • n個の石の山があり、各山の高さs_iが与えられる。プレイヤーは交互に、1つの山から1つ以上の石を取り除いていく。動かせなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 典型Nim
  • HackerRank - Misère Nim
    • Nimの逆形をする（最後に石を取り除いた方が負け）。先手と後手どちらが勝つか求めよ。
  • HackerRank - Nimble Game
    • n個のマスがあり0からn - 1まで番号が振られている。各マスにはc_i個のコインが置いてある。プレイヤーは交互にコインをひとつマスiからj(0 <= j < i)に移していく。動かせなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • c_i個あるコインをc_i個の山とみなすとNimになる。
  • HackerRank - Poker Nim
    • n個の石の山があり、各山の高さs_iが与えられる。各プレイヤーは交互に以下のどちらかの操作をする。1. ひとつの山から1つ以上の石を取り除く。2. ひとつの山に1つ以上の石を追加する。ただし、どの山にもk回までしか石を追加する操作はできない。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 追加できるが後手はそれ以上を減らすことで無向化できるのでただのNimになる
  • HackerRank - Chocolate in Box
    • Nimゲームをする．先手が勝つような石のとり方はいくつあるか（先手が勝つことが保証されている）．
    • 全体xorが0になるような取り方をだす．山iを除いたxorをだすためには山iと全体のxorをとればいい．その数が山iより小さければxorを0にすることができるので，そのような山をカウントする．
  • HackerRank - Vertical Rooks

Grundy数

概要

まずGrundy数の計算方法について。負け状態のGrundy数を0とする。今の状態から1回の操作で遷移できるGrundy数の集合に含まれていない最小の非負整数をGrundy数とする。
Nim山もGrundy数も1回の操作で自身以下の数にすることができるため、Grundy数はNimの１つの山とみなすことができる。そのため、すべての状態のGrundy数をだせばNimに帰着することができ、xorをとることで勝負の判定ができる。

問題

  • yukicoder - No.8 N言っちゃダメゲーム
    • 自然数NとKが与えられる。プレイヤーは交互に[1, K]のどれかを加算することができる。0からはじめ、N以上になったら負け。先手と後手どちらが勝つか求めよ。
    • わざわざGrundy数を考える必要ないけど練習のため
  • HackerRnak - Tower Breakers, Revisited!
    • タワーがN個ある。各タワーの高さh_iが与えられる。プレイヤーは交互に高さXのタワーを高さYにしていく。ここでYはX未満のXの約数である。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 遷移先は約数
  • HackerRank - ower Breakers, Again!
    • タワーがN個ある。各タワーの高さh_iが与えられる。プレイヤーは交互に高さXのタワーを高さZのY個のタワーにしていく。ここでYとZはY × Z = XかつY > 1を満たす数である。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 増える系。Grundyをマージするテク
  • HackerRank - Zero-Move Nim
    • Nimゲームをするが、各プレイヤーは各山に対して一度だけパスができる。例えば山iに対してプレイヤー１がパスをしたら、プレイヤー2は山iに対してはパスはできない。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • Grundy数を計算する。状態はパスをしたときとしてないときの2つある。パスをしていない状態からはパスをした状態にいけるので、そこを考慮してGrundy数を計算する。
  • HackerRank - Chessboard Game, Again!
  • HackerRank - Deforestation
    • ノード1を根とした木がある。プレイヤーは交互にエッジを選び取り除いていく。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 各ノードのGrundy数を計算する。
  • AGC017 - D Game on Tree
  • ARC038 - C 茶碗と豆
    • N個の茶碗があり横一列に並んでいる。各茶碗にわ整数C_iとA_i個の豆が定義されている。茶碗0は整数が定義されず、豆もない。プレイヤーは交互に茶碗iから豆をひとつだし、i - C_iからi - 1の茶碗のどれかにいれる。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
    • 各茶碗のGrundy数を計算する。豆ひとつだけのゲームが複数回あると考えるとわかりやすい？
  • ARC013 - C 笑いを取れるかな？
    • N個の豆腐があり，各サイズがあたえられる．豆腐にはそれぞれM_i個のハバネロがある．プレイヤーは交互に豆腐を切り取っていく．ハバネロがある箇所を切り取った方が負け．先手と後手どちらが勝つか求めよ。
    • 豆腐の上，下，左，右，奥，手前をNim石に見立てることでGrundy数を求めることができる．

Adhoc系

概要

いろいろ。

問題

  • 相手を真似る
    • HackerRank - Tower Breakers
      • 高さMのタワーがN個ある。プレイヤーは交互に高さXのタワーを高さYにしていく。ここでYはX未満のXの約数である。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
  • 偶奇
    • HackerRank - Alice and Bob’s Silly Game
      • 1からnまでの集合がある。プレイヤーは交互に素数を選び、その素数とその倍数を取り除いていく。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
      • 状態削減と偶奇
  • その他
    • ABC059 - D Alice&Brown
      • X個、Y個の石がおかれた山がある。プレイヤーは片方の山から2i個の石をとり、i個を捨て残りのi個をもう片方の山におく。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
      • 普遍量を考える。ここでは差。
    • ABC048 - D An Ordinary Game
      • 文字列sがある。プレイヤーは交互に、sの中に同じ文字が隣り合わないように文字をひとつ取り除く。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
      • 最終形を考える。
    • ARC046 - B 石取り大作戦
      • N個の石がある。プレイヤーは交互に石を取り除いていく。先手はA個まで、後手はB個まで石をとれる。動けなくなった方が負け。先手と後手どちらが勝つか求めよ。
      • Nimのとれる個数が違う版。
  • 最善戦略
    • ABC067 - D Fennec VS. Snuke
      • N個のノードからなる木がある。1番目のノードは黒く、N番目のノードは白い。先手は黒いノードの隣接した未着色のノードを黒く塗れる。後手は白いノードの隣接した未着色のノードを白く塗れる。色を塗れなくなった方が負け。先手と後手どちらが勝つか求めよ。
      • 1からNまでのパス上のノードを塗っていくのが最善。

最大化/最小化

  • 貪欲

    • ARC038 - A カードと兄弟
      • N枚のカードがあり、各カードには整数A_iが書かれている。各プレイヤーは好きなカードを1枚ずつ選んでいく。選んだカードの和をスコアとする。先手のスコアを求めよ。
    • ABC046 - D AtCoDeerくんと変なじゃんけん
      • グーとパーしかだせないじゃんけんをN回する。各ターンで今までにパーを出した回数 ≦ 今までにグーを出した回数を満たす必要がある。相手の手がわかっているとき勝ちの回数を最大化せよ

  • 最善戦略

    • ARC085 - D ABS
      • N枚のカードがあり、それぞれ整数がかかれている。XさんとYさんははじめZ, Wがかかれたカードをもっている。Xから交互にカードを1枚以上引き、最後に引いたカードをもつ。最終的に2人の持っているカードの差の絶対値がスコアになる。Xはスコアを最大化するように、Yは最小化するように行動したときスコアはいくつになるか
      • 先手が全部とるか1つ残すかする。後手に考慮の余地がないゲームはよくある気がする。ゲームDPでもとける。
    • HackerRank - Fun Game
      • n個の要素からなる配列AとBがある．各プレイヤーはインデックスiを選び，先手ならA[i]点を後手ならB[i]点を得る．ただし，先手と後手で同じiを選ぶことはできない（そのためnターンで終わる）．両者が得点を最大化しようとしたときどちらが勝つか求めよ．
      • A[i] + B[i]が最大となるiをとるのが最善．

  • ゲーム木

    • ABC025 - C 双子と○×ゲーム
      • 3×3のマスがある。交互に○と×を書いていく。ある列で同じ文字がかかれていたら先手にb_ij点、ある行で同じ文字が書かれていたら後手にc_ij点入る。最善をつくしたときの両者の得点を求めよ
  • ゲームDP

その他

問題

考えること

  • 独立している複数のゲームに分割できるか
  • 偶奇で分類できないか
  • ゴールまでの距離で分類できないか
  • Nimに帰着できるか
  • Grundy数をだせるか

参考

未分類