Codeforces Round #406 (Div. 2): C.Berzerk
問題
解法
終点(x=0)から逆に辿って行く動的計画法。
Mortyにx=0で手番が回ってくる(つまりMortyの敗北)前の手番では、Rickによってモンスターはx=n-s[0][i](ある0<=i<k1)から遷移してきているので、その座標にRickの手番が来た時はRickの勝利である。その座標に辿り着く場合は
①その座標がスタート地点
②Mortyの手番でx=n-s[0][i]-s[1][j](ある0<=j<k2)から遷移してきた
の二通りが考えられる。
②の場合は、問題の前提から、Mortyによってモンスターがx=n-s[0][i]へ遷移するのは他の全ての手もMortyの敗北である時だけと分かる。つまり、x=n-s[0][i]-s[1][j]からのMortyによる遷移はx=n-s[0][l](任意の0<=l<k1)のいずれかであることが保証できれば、x=n-s[0][i]-s[1][j]の座標でMortyが来た時は敗北する。ここまでを終点をx=n-s[0][i]-s[1][j]にして繰り返す。
終わったら、Rickにx=0で手番が回ってくる場合でもう一度計算をする。
確定されなかった点はLOOPになる。
ソース
参考
kimiyukiさんの実装を参考(というかそのまま)にした。
Codeforces Round #406 (Div. 1): A. Berzerk · うさぎ小屋
c++の論理否定!の代替表現のnotを初めて知った(小並感)