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
- これを実装すると1つのテストケースを除いて通る
- テストケース urchin (ウニ) でTLE
- 始点の隣はO(N)個あり、それらの周辺を調べるのでO(N2)
高速化が必要
- kmjpさんのBlogを見て分かったが、辺を張るときに「隣に青がいるか」「隣に赤がいるか」の情報を事前に作れる
- それを使って「Kが偶数・始点がB」の時の判定すればAC