ARC078 D Fennec VS Snuke

問題概要

1番が黒、N番が白く塗られた木に対し、自分の色に隣接しているノードに先手は黒、後手は白を塗っていくゲームをする、先に色が塗れなくなったほうが負けの時、両者が最適な動きをした場合勝つのはどちらかを求めよ。

取った方針

木はあるノードからあるノードまでのパスが一つしかないため、先手はN番、後手は1番を目指して塗っていくのが最適である。
そのように塗っていった場合、先手後手それぞれが塗れるノードは一意に定まる。具体的には、ノード1からの距離とノードNからの距離をそれぞれd_1,d_nとおくと、
d_1 >= d_nの時、そのノードは黒
そうでない時そのノードは白となる。
それはスタート地点からの距離が近い方がそのノードに色を塗るからである。また、黒が先手であるので、同じ場合は黒が塗ることとなる。
よって、1,Nそれぞれを始点とするBFSをして、塗れるノードが多い方が勝ちとなる。

正しい方針(解説の方針)

同上

得られた知見

・木の性質として、ノードiからノードjに行くパスは一意に定まる。
・BFS

解くのに必要な要素

・木の性質
・BFS

周辺調査によって得られた知見

なし