Create a gist now

Instantly share code, notes, and snippets.

@yosupo06 /train.txt Secret
Last active Jul 31, 2017

What would you like to do?
毎回行く辺を決めることにしても、勝敗は変わらないだろうと仮定する(未証明)、無限回移動出来るならAの勝ち
頂点を倍加して、(頂点, 燃料)にする
給油所(u, *)からは(v, N+1)に辺を貼る
非給油所(u, p+1)からは(v, p)に辺を貼る、(u, 0)からはどこにも貼らない
頂点ごとにAが移動させるかBが移動させるか決まってるので、無限回移動できるか?を求めたい(Bは意地悪をする)
これは頂点ごとに、(無限回移動できる頂点の個数)みたいなのを持って後退解析?芋づる式更新?みたいなことをすればよい
A所有頂点なら、1個以上残っていれば自分もOK、B所有なら、全部残ってないとダメ
定数倍バトル
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment