yukicoder No.374 コイン
問題
2人で以下のゲームを行う。
・半径Aの円の中に、半径Bの円を交互に置いていく
・置いていく円は、半径Aの円からはみ出したり、すでに置いた円とかさなったりしてはいけない
・先に置けなくなった方が負け
・置かれた円は動かせない
それぞれ最適に行動した場合、どちらが勝つか答える。
制約
1 <= A,B <= 2^32
解説
A < Bの場合、先手がすでにおけないので、後手の勝ち。
A >= Bの場合を考える。
2*A/3 < Bの場合は、真ん中に置くと、その後、どこにも置けなくなるので、先手の勝ちということがわかる。
2*A/3 >= Bの場合は、先手がどこに置いても後手に手番が回る。
最適な行動は、まず、真ん中に置いて、後手に手番をわたす。
後手がどこに置いたとしても、「円の中心の点対称の位置に円を置く」ということを繰り返すと、必ず先手はおくことができる。
したがって、先手がこの行動をとった場合、必ず勝てるので、先手の勝ちとなる。
