CADDi 2018-D "Harlequin"

いや難しすぎません？コレ

提出コード

考察

次の2つの状況を考えます．

状況A：任意の種類のりんごが偶数個である

状況B：少なくとも1種類，奇数個のりんごがある

各プレイヤーが最適にりんごを食べるとき，状況Aに遭遇したプレイヤーが負けることが次のように示されます．

(つまり，状況Bに逃げるという選択肢が最適な食べ方です)

まず状況Bにいる場合，奇数個残っているりんご(の種類)を全て1個ずつ食べることで状況Aを作り出して相手に渡せます．

ここで，相手がどのような食べ方をしても状況Bになって自分の番が来ます．

そして初めの手順と同じように奇数個残っているりんご(の種類)を全て1個ずつ食べて相手に状況Aを渡します．

(なお，2回目以降は相手が食べたりんごの食べ方と全く同じように食べればOK)

これを繰り返すことで自分が全てのりんごを食べる番がやってきます．

(言い換えると，全てのりんごが0個という状況Aを作り出して相手に渡せます．)

以上より，状況Aに遭遇したプレイヤーが負けることが示ました．

最初のターンは自分と決まっているので，初めに与えられる状況がAであれば自分の負け，Bであれば自分の勝ちです．

奇数や偶数が関連しそうなあたりは目星がついていましたが最終的な発想は全然出てきませんでした．