Quiz
https://atcoder.jp/contests/agc033/tasks/agc033_c
Submission
https://atcoder.jp/contests/agc033/submissions/5293995
木の直径
- 上記問題で木の直径を求める必要があったのでbfsで求めた
C, 直径という大局から見るのかぁ
— peroon_cp (@peroon_cp) 2019年5月4日
上記問題 C - Removing Coins について
- 木の直径に帰着できれば、Nimのゲームの問題になる
- 直径dを互いに1 or 2ずつ減らしていきd=1になると、その時の木は o-o という形になっていて、その手番で取ると o のみ残り、相手が最後のコインを取る
- よって、d=1を押し付けられれば勝ち
- 1 or 2取るゲームなので、3の剰余で考える
- 下図より、(d-1)%3==0なら負け
