# D - Harlequin (opens new window)
# 概要
- 色のりんごが個ある
- あなたと相手で以下の行動をあなたから交互に行う
- 個以上の異なる種類のりんごを選んで食べる
- 最後のりんごを食べた者を勝者とする
# 思考
- Nimっぽい?
- 実験してみる
- Nimかもしれない
- 投げる
- WA
- 別解法を模索する
ここで30分終了
- N=2の時で考える
- この時二次元の表で考えられるので, その表をわかる部分から埋めていく
- 最低でも
0 0
の時, 負けが確定している- この状態で相手に渡せば, 勝ちが確定する
- 言い換えれば, その状態にできる状態が勝利状態(以下の状態)
0 1
1 0
1 1
# 解法
- 入力が全て偶数なら負け確定なので相手(Second)の勝ち
- 逆に1つでも奇数があれば自分(First)の勝ち
# ゲーム理論の最適解の考え方
相手がどういう操作をしても必ず勝てる方法(もしくは負ける方法)を探す
- 有限回で終わるものは最適解がわかりやすい
その状態を相手に渡すためにどうすれば良いのか考える
その状態を相手に渡せる範囲はどこまでなのかを考える
それを繰り返すことで一般化できる
基本的には実際に表などにして実験すると良い
まとめておくと発想が湧きやすい