# D - Harlequin (opens new window)

# 概要

  • NN色のりんごがaia_i個ある
  • あなたと相手で以下の行動をあなたから交互に行う
    • 11個以上の異なる種類のりんごを選んで食べる
  • 最後のりんごを食べた者を勝者とする

# 思考

  • Nimっぽい?
  • 実験してみる
  • Nimかもしれない
  • 投げる
    • WA
  • 別解法を模索する

ここで30分終了

  • N=2の時で考える
  • この時二次元の表で考えられるので, その表をわかる部分から埋めていく
  • 最低でも0 0の時, 負けが確定している
    • この状態で相手に渡せば, 勝ちが確定する
    • 言い換えれば, その状態にできる状態が勝利状態(以下の状態)
      • 0 1
      • 1 0
      • 1 1

# 解法

  • 入力が全て偶数なら負け確定なので相手(Second)の勝ち
  • 逆に1つでも奇数があれば自分(First)の勝ち

# ゲーム理論の最適解の考え方

  • 相手がどういう操作をしても必ず勝てる方法(もしくは負ける方法)を探す

    • 有限回で終わるものは最適解がわかりやすい
  • その状態を相手に渡すためにどうすれば良いのか考える

  • その状態を相手に渡せる範囲はどこまでなのかを考える

  • それを繰り返すことで一般化できる

  • 基本的には実際に表などにして実験すると良い

  • まとめておくと発想が湧きやすい

# 提出

Last Updated: 1年前