木の直径 (エッジコスト1バージョン)

Quiz

https://atcoder.jp/contests/agc033/tasks/agc033_c

Submission

https://atcoder.jp/contests/agc033/submissions/5293995

木の直径

  • 上記問題で木の直径を求める必要があったのでbfsで求めた

上記問題 C - Removing Coins について

  • 木の直径に帰着できれば、Nimのゲームの問題になる
  • 直径dを互いに1 or 2ずつ減らしていきd=1になると、その時の木は o-o という形になっていて、その手番で取ると o のみ残り、相手が最後のコインを取る
  • よって、d=1を押し付けられれば勝ち
  • 1 or 2取るゲームなので、3の剰余で考える
  • 下図より、(d-1)%3==0なら負け

f:id:peroon:20190507000151j:plain