CADDi 2018 | D - Harlequin

問題

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b

解法

$N=1$のときについて考えると以下である。

1色しかないりんごを1つづつ交互に取得していくので奇数のときに自分が勝ち、偶数のときにルンルンが勝つ。

$N=2$のときは以下になる。

りんごは2色で2色とも偶数のときにルンルンが勝ち、それ以外は自分が勝つ。

なんとなく偶奇が関係しそうである。

各色のりんごがすべて偶数の状態を$E$とし、奇数がひとつでもある状態を$O$とする。

先行が自分で、りんごが1色のときは初期状態が$E$だと負けて、$O$だと勝てる。

りんごが1色より多い時を考える。
初期状態がすべて偶数の$E$の状態だとどのように行動してもルンルンに同じ色のりんごを同じ数だけとれば$E$で自分にかえってきてしまう(りんごがもう無い場合はとらない)。
初期状態が$O$の場合は奇数のりんごだけとってルンルンに$E$を渡せるので必ず勝てる。

よってまとめると、りんごの数がすべて偶数のときは後攻が勝ち、それ以外は先行が勝つ。

コード

実装時のTips

参考

https://atcoder.jp/contests/caddi2018/editorial