Codeforces Round #406 (Div. 2): C.Berzerk

問題

codeforces.com

解法

終点(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を初めて知った(小並感)

CとC++の演算子 - Wikipedia