Grundy数
ゴール
ABCに出たら絶対解く
いずれARC-Cを倒す
前提
2山Nimでググる
証明は日本語で無数に出てくる
ニム(複数山の石取りゲーム)の必勝法
組み合わせゲーム理論の基礎とGrundy数での勝敗判定アルゴリズム
石取りゲームの数学: ゲームと代数の不思議な関係
3章あたりまででNimの数学が十分分かる。競プロに役立ちそう
以降も色々な変形やその数理的解析があり面白い。競プロに役立つかは知らない
基本問題
No.2 素因数ゲーム
提出
典型問題
典型90 031 - VS AtCoder(★6)
局面数をちゃんと見積もる
ABC297-G - Constrained Nim 2
まぁ実験してエスパーするだけ
考えると、「X個取られたらY取る」が可能なR+L周期と分かる
応用問題
いつか解く
TODO
https://yukicoder.me/problems/no/103
https://atcoder.jp/contests/arc038/tasks/arc038_b
https://atcoder.jp/contests/arc013/tasks/arc013_3
https://yukicoder.me/problems/no/1363
https://yukicoder.me/problems/no/524
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0401&lang=ja