A - Taro vs. Jiro

Quiz

https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_a

Submit

https://atcoder.jp/contests/dwacon5th-final-open/submissions/4625049

Kが奇数の場合

  • 最後の一手を打てる太郎有利
    • 始点の隣にBがある→太郎勝ち
    • 始点の隣にRしかない→次郎勝ち

Kが偶数の場合

  • 最後の一手を打てる次郎有利
    • 始点がR→次郎勝ち
    • 始点がB
      • 始点の隣の点から見て、周りが全てBのものがある→太郎勝ち
      • それがない→2手でRに誘導されるので次郎勝ち

TLE

高速化が必要

  • kmjpさんのBlogを見て分かったが、辺を張るときに「隣に青がいるか」「隣に赤がいるか」の情報を事前に作れる
  • それを使って「Kが偶数・始点がB」の時の判定すればAC