grundy数を初めて使ってみた Day 1: Game of Stones

Quiz

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones/problem

Submit

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones/submissions/code/1314174009

grundy数とは

https://www.slideshare.net/chokudai/arc038

その他

  • Nimは分かってきたがgrundy数を使ったのは初めて
  • 相手をコントロールできる位置をキープできれば勝てる、というのを一般化したものがgrundy数なのだろう
  • なので知らなくても解ける
    • 上記問題のeditorialでもgrundy数という言葉は出てこない

計算量

  • 長さNの配列を埋めるのにO(3*N) = O(N)
  • それを使ってQクエリを処理するので、全体ではO(N+Q)

Nim

  • 各山のXOR=0で負け。それ以外で勝ち

Grundy

  • 複数のゲームがあってそれぞれGrundy数が求まる場合、それらのXOR=0なら負け。それ以外で勝ち
  • 動けないならGrundy=0
  • Grundy=0の状態に到達できるなら1, 2, ..と増えていくが、1より大きい値そのものには意味がある?
    • (→たぶん各ゲームそれぞれのGrundy数を求めてXORで統合する時に効いてくる)

モノマネ

実験

  • しよう

Grundy数の統合について

  • mexするのかXORするのかで迷う
  • 状態A→Bに状態遷移しうるならmex
  • (Nimの各山のように)どれかを選んで変化させるのは、各Grundy数のXORで統合

実戦:HackerRank 15問(14問解きます)

  • 問題集:https://www.hackerrank.com/contests/5-days-of-game-theory/challenges
  • Day 1: Game of Stones : 解法:Grundy数, setで求めた
  • Day 1: Tower Breakers : N本の「同じ高さの」塔があり、(高さ1まで)削っていく。解法:モノマネ
  • Day 1: A Chessboard Game : 移動先がLoseしかないならWin
  • Day 2: Nim Game : Nimそのもの
  • Day 2: Misère Nim :
    • 山の高さ=1は例外対応 *(全山の)最後の石をとったら負けのゲーム。場をコントロールできるので基本的に勝てるが、XOR=0の時のみ負ける
    • 1111xの時にxからx-1個とって11111を押し付ける
  • Day 2: Nimble Game : 横のNimと見ることができる。A⊕A=0なので同じ高さの山がいくつあっても偶奇だけえ見ればいい
  • Day 2: Poker Nim : 積んでも「打ち消し」できるので、一般的なNimとおなじになる。XOR=0で判定
  • Day 2: Tower Breakers, Revisited! : 素因数分解したときの素因数の数を山の高さとしたNim. (12=2x2x3なのでこのときは高さ3)
    • パターン:○○を山の高さとしたNim
  • Day 3: Tower Breakers, Again! : 山を約数で割った後「分裂」するバージョン。
    • 山の高さの約数一覧列挙
    • それぞれで割った塔たちのまとまりからGrundy数を求める。それらから、割る前の塔のGrundy数が求まる。XORして判定
  • Day 3: Chessboard Game, Again! : Grundy数のXOR。16x16ではなく15x15の盤面であることに注意
  • Day 3: Digits Square Board : グリッドを分割する。分割した2つのグリッドのXORを、次に行ける状態のGrundy数そして列挙してmexでGrundy数を決める
    • 分割したGrundy数はXORで統合
    • 各切り方で求めたGrundy数から自分のGrundy数を決めるにはmex
    • 高速化が必要。範囲が全部primeかの判定に累積和、mexにはsetじゃなくてvectorを使う必要があった
  • Day 4: Fun Game 意外と簡単だった。A+Bが取る優先度
  • Day 4: Powers Game :
    • 実験
    // experiment
    rep(i, 30){
      debug(i, ll_pow(2, i)%17);
    }
    return 0;
[i, ll_pow(2, i)%17]: 0 1
[i, ll_pow(2, i)%17]: 1 2
[i, ll_pow(2, i)%17]: 2 4
[i, ll_pow(2, i)%17]: 3 8
[i, ll_pow(2, i)%17]: 4 16
[i, ll_pow(2, i)%17]: 5 15
[i, ll_pow(2, i)%17]: 6 13
[i, ll_pow(2, i)%17]: 7 9

[i, ll_pow(2, i)%17]: 8 1
[i, ll_pow(2, i)%17]: 9 2
[i, ll_pow(2, i)%17]: 10 4
[i, ll_pow(2, i)%17]: 11 8
[i, ll_pow(2, i)%17]: 12 16
[i, ll_pow(2, i)%17]: 13 15
[i, ll_pow(2, i)%17]: 14 13
[i, ll_pow(2, i)%17]: 15 9

[i, ll_pow(2, i)%17]: 16 1
[i, ll_pow(2, i)%17]: 17 2
[i, ll_pow(2, i)%17]: 18 4
[i, ll_pow(2, i)%17]: 19 8
[i, ll_pow(2, i)%17]: 20 16
[i, ll_pow(2, i)%17]: 21 15
[i, ll_pow(2, i)%17]: 22 13
[i, ll_pow(2, i)%17]: 23 9
[i, ll_pow(2, i)%17]: 24 1

[i, ll_pow(2, i)%17]: 25 2
[i, ll_pow(2, i)%17]: 26 4
[i, ll_pow(2, i)%17]: 27 8
[i, ll_pow(2, i)%17]: 28 16
[i, ll_pow(2, i)%17]: 29 15
  • 8の倍数だとモノマネされて負ける
  • 逆に9など奇数だと、あふれた(対応するmodのない)ものを最初に取り、あとはモノマネすればmod 17の結果が0以外で終われる
  • 偶数、たとえば6だとどうだろう。対応するものを相手がぶつけてこれないので、こちらの勝ち
  • ポイントは「実験」

  • Day 5: Deforestation :

    • テストケース1でBobが動けない理由がわからない
    • dfs内でXOR ^= dfs() + 1
    • +1がポイントだった
    • 「あなたの茎(stalk)の長さは?」子どもたちのXOR + 1(自分の分)