Skip to content

Instantly share code, notes, and snippets.

@yosupo06

yosupo06/train.txt Secret

Last active July 31, 2017 07:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yosupo06/bc43d48f56b8e1b3e54e5ad359ceea7a to your computer and use it in GitHub Desktop.
Save yosupo06/bc43d48f56b8e1b3e54e5ad359ceea7a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
train.txt
毎回行く辺を決めることにしても、勝敗は変わらないだろうと仮定する(未証明)、無限回移動出来るなら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