ferinの競プロ帳

競プロについてのメモ

Codeforces Round #429 (Div. 2) B. Godsend

問題ページ
Problem - B - Codeforces

概要

n要素の数列が与えられる。player1は合計が奇数、player2は合計が偶数になる区間を選択して取り除くことができる。
行動できなかったら負け。勝つ方を求める。

解法

最初の数列の合計が奇数個だったら当然Firstの勝ち。
最初の数列の合計が偶数でFirstが行動できたとしたら合計は奇数になる。
Secondが合計が偶数の区間を取れたとしても次にFirstに合計が奇数で回ってくるのでFirstの勝ち。
よって数列に奇数が一個でもあったらFirstの勝ち。