- Quiz
- AC (要ログイン)
- 計算量
- 長さNの配列を埋めるのにO(3*N) = O(N)
- それを使ってQクエリを処理するので、全体ではO(N+Q)
Nim
- 定義
- 複数の石の山がある
- 1つ山を選び、1つ以上の石を取りのぞく
- 石を取れなくなった(動けなくなった)方の負け
- 各山のXOR=0で負け。それ以外で勝ち
- この設定のNimでは「石の数=Grundy数」
Grundy数
- 遷移先のGrundy数の集合に含まれない最小の非負整数
- 相手をコントロールできる位置をキープできれば勝てる、というのを一般化したもの?
- 複数のゲームがあってそれぞれGrundy数が求まる場合、それらのXOR=0なら負け。それ以外で勝ち
- 動けないならGrundy=0
- Grundy=0の状態に到達できるなら1, 2, ..と増えていくが、1より大きい値そのものには意味はある?
- (→たぶん各ゲームそれぞれのGrundy数を求めてXORで統合する時に効いてくる)
モノマネ
- マネをすれば勝てる場合、Grundy数を求めるよりシンプルに解ける
実験
- しよう
Grundy数の統合について
- mexするのかXORするのかで迷う
- 状態A→Bに状態遷移しうるならmex
- (Nimの各山のように)どれかを選んで変化させるのは、各Grundy数のXORで統合
ゲームで取れる手段
Nim, Grundy, mex, xor モノマネ 実験 メモ化再帰(DAGの場合) 後退解析(閉路ありの場合)
実戦: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! : 山を約数で割った後「分裂」するバージョン。
- Day 3: Chessboard Game, Again! : Grundy数のXOR。16x16ではなく15x15の盤面であることに注意
- Day 3: Digits Square Board : グリッドを分割する。分割した2つのグリッドのXORを、次に行ける状態のGrundy数そして列挙してmexでGrundy数を決める
- 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(自分の分)