🙌

CADDi 2018 | D - Harlequin

1 min read

問題

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

Discussion

ログインするとコメントできます