Game

AGC017D: Game on Tree

http://agc017.contest.atcoder.jp/tasks/agc017_d(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvか…

grundy数

grundy数について勉強したのでお話します。grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。 2.grundy数=kの…

AtCoder Regular Contest 078D: Fennec VS. Snuke

http://arc078.contest.atcoder.jp/tasks/arc078_b解法自体は簡単だけど、バグらせたので。 こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。 [a (a+b)/2)にすると半分、またはそれより1小さくなり、 [a (a+b+1)/2)にすると半分、また…

AtCoder Regular Contest 072D: Alice&Brown

http://arc072.contest.atcoder.jp/tasks/arc072_bゲームこわいと思ったが、終了状態が(0,1)か(1,1)なのだから、そこからbacktrackしたら結局abs(X-Y) (Brownの勝利)となることがすぐわかる。 ll N, M; void solve() { cin >> N >> M; if(abs(N - M) <= 1) c…